問題
The prime factors of 13195 are 5, 7, 13 and 29.
Problem 3 - Project Euler
What is the largest prime factor of the number 600851475143 ?![]()
13195 の素因数は 5、7、13、29 である。
Problem 3 - PukiWiki
600851475143 の素因数のうち最大のものを求めよ。![]()
素因数分解の問題ですね。
回答
Groovyで解いてみた (2012-08-20 更新)
まずは、素数の無限数列のイテレータを定義。
@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]
- 問題の答えは、一番大きな素数ですので 6857 が答えとなります。