Project Eulerの問題をMatlab/Octaveで解いてみる3問目。
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?13195の素因数は5、7、13、29である。600851475143の素因数のうち最大のものは何か?
という問題。Matlabにはprimesという関数があるので、横着してそれを使ってしまいます。
num = 600851475143; p = primes(sqrt(num)); for n=length(p):-1:1 if mod(num, p(n)) == 0 disp(p(n)); num = num / p(n); end end
指定された数をnumに入れ、√numまでの素数リストをprimesで作成します。素数リストの大きい方から順に、numを割り切れるかを調べていきます。最初に割り切れる素数が、求めている最大の素因数となります。
そこで終わっても良いのですが、せっかくなので、すべての素因数をリストアップするようにしています。