この問題は以前に詳しく説明しました。
要約すると、
dは素数でなければならない
10n ≡ 1(mod d)となる最小の自然数nはd-1でなければならない
上の合同式が成り立つnはd-1の約数のみ
だから、d-1以外の全ての約数について上の合同式が成り立たないような最も大きいdを求めればよいのでした。
しかし、もう少し考えるとd-1から一つずつ素因数を取り除いた数、すなわち例えば
d - 1 = 23・32・5
だとすると、
22・32・5
23・3・5
23・32
の3つについて調べていずれも合同式が成り立たないことを確かめればよいです。
もっとも、この計算より素数判定のほうがずっと遅くて、速度的には約数全部調べるのとあまり変わらないのではないかと思います。
import scala.testing.Benchmark def is_prime(n :Int) = Iterator.from(2).takeWhile(m => m * m <= n).forall(n % _ != 0) def factorize(n :Int) = { def f(n :Int, p :Int) :List[Int] = { n match { case 1 => Nil case _ if p * p > n => List(n) case _ if n % p == 0 => p :: f(n / p, p) case _ => f(n, p + 1) } } f(n, 2).groupBy((x) => x).toList.map((x) =>(x._1, x._2.length)) } def pow(n :Int, e :Int, d :Int) :Int = if(e == 0) 1 else { val m = pow(n, e / 2, d) if(e % 2 == 1) (m.toLong * m * n % d).toInt else (m.toLong * m % d).toInt } def is_full_length(n :Int) = is_prime(n) && factorize(n - 1).map((n - 1) / _._1).forall(pow(10, _, n) != 1) def solve() = { val N = 1e9.toInt println (Iterator.range(N - 1, 1, -1).filter(is_full_length).next) } object Test extends Benchmark { def run() = solve } println (Test.runBenchmark(10))