当メモは2012-08-20に投稿されたものを加筆修正し、再掲したものです。
みなさまもお好きな言語で解いてみてくださいね。
目次
お題
素因数分解の問題ですね。
英語
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 の素因数のうち最大のものを求めよ。
Groovyで解いてみた
2012-08-20 更新- こちら より抜粋
まずは、素数の無限数列のイテレータを定義します。
@CompileStatic class Primes implements Iterator{ 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 ListtoPrimeFactors(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が答えとなります。