Project Euler Problem 3 を解いてみた

問題

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Problem 3 - Project Euler

13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。
Problem 3 - PukiWiki

素因数分解の問題ですね。

回答

Groovyで解いてみた (2012-08-20 更新)

https://github.com/fumokmm/project-euler-solve/blob/master/problems/3/problem3.groovy より抜粋

まずは、素数の無限数列のイテレータを定義。

@CompileStatic
class Primes implements Iterator<BigInteger> {
  private BigInteger p = 1G
  @Override boolean hasNext() { true }
  @Override BigInteger next() {
    this.p = this.p.nextProbablePrime()
    this.p
  }
  @Override void remove() { throw new UnsupportedOperationException() }
  @Override String toString() { p }
}

素数かどうかの判定にはおなじみ、BigInteger#nextProbablePrime() を利用しています。

せっかくの機会なので、Groovy2.0から使えるようになった静的コンパイルチェックを利用してみています。@CompileStaticアノテーションを利用していますので、以下のimportが必要です。
import groovy.transform.CompileStatic
Groovy2.0の静的コンパイルについてはこちらが詳しいです。

今回は "素数の小さい方から割る" という単純な方法でやっつけました。以下がロジック本体です。

@CompileStatic
List<BigInteger> toPrimeFactors(BigInteger num) {
  def rslt = []
  def primes = new Primes()
  while (num > 1) {
    BigInteger p = primes.next()
    while (num.mod(p) == 0G) {
      rslt << p
      num /= p
    }
  }
  rslt
}

assert toPrimeFactors(13195) == [5, 7, 13, 29]
assert toPrimeFactors(600851475143) == [71, 839, 1471, 6857]