Project Eulerに挑戦: 問題3

Table of Contents

問題3

600851475143の最大の素因数を求めよ.

Cで解く

600851475143は 231 以上であり,64ビット整数を用いる必要がある. gccではlong longで64ビット整数を用いることができる.

 1:  long long e003() {
 2:      long long n = 600851475143LL;
 3:      long long k = 2;
 4:      while (k*k <= n) {
 5:          while (n % k == 0)
 6:              n /= k;
 7:          k++;
 8:      }
 9:      return n == 1 ? k : n;
10:  }
  • このプログラム間違っていそうですね… 後日修正します…

Scalaで解く

素因数のリストを求める関数を作成する.

1:  def factor(n: Long, p: Long): List[Long] =
2:    if (n < p * p)
3:      List(n)
4:    else if (n % p == 0)
5:      p :: factor(n / p, p)
6:    else
7:      factor(n, p + 1)
8:  def factor(n: Long): List[Long] = factor(n, 2)

factorの実行結果は以下のようになる.

scala> factor(8)
res: List[Long] = List(2, 2, 2)

scala> factor(2310)
res: List[Long] = List(2, 3, 5, 7, 11)

したがって回答は以下で求められる.

scala> factor(600851475143L).last

手で解く

Wolfram Alpha で600851475143を入力し,素因数分解の結果を見る.

Linuxのfactorコマンドを用いる.

$ factor 600851475143

Date: 2017-09-29 21:44:13 JST

Author: 田村直之

Validate XHTML 1.0