Project Euler No.3

R1001679.JPG

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を割り切れるかを調べていきます。最初に割り切れる素数が、求めている最大の素因数となります。

そこで終わっても良いのですが、せっかくなので、すべての素因数をリストアップするようにしています。