この問題はある意味難しいです。
1, 3, 7, 9の4つの数字だけ作って、回して全てが素数かどうか調べればいいので簡単です。ただ、例えば197が「回転素数」だったとして、197・971・719に対して素数判定だったとします。そうすると、719についてもやっぱり3回素数判定をしなければなりません。971も同じです。だから無駄がありますね。これを避けるために回転して最小の数だけ「回転素数」の判定を行います。上の例なら197のときだけ判定します。これが下のコードです。
しかし、一々回転して最小かどうか判定するのは無駄が多い気がします。例えば、頭が1で残りが3、7、9なら明らかに「回転最小」ですね。逆に頭が3でどこかに1があれば「回転最小」ではありません。このように判定せずにいきなり「回転最小」を漏れなく生成できないでしょうか。
これが難しいんです。わかりやすくするために、1が使われているとして、1のみのブロックと1が使われていないブロックに分けます。
11 3 1 7 1 9
最初に1が2つ来て、あと2つ以上続くブロックはないので、これは「回転最小」です。では、これはどうでしょう。
1 33 1 7 1 9
1のブロックはみな同じなので、こういうときはそれ以外のブロックを比較します。最初が1番小さいのでこれは「回転最小」です。ここで33が7と9に比べて小さいと言っているのは、頭から数字を比べてです。この場合頭で大小が決まっています。そこで決まらなければ次の桁を見ます。33と3は3は次の桁がないので3のほうが小さいと解釈します。ではこういうのはどうでしょう。
1 3 1 7 1 3 1 3 1 9
わかりにくいですよね。このように一般に最小かどうかを判定するのは難しいのです。いわんや「回転最小」だけを生成するのは大変そうです。
def is_prime(n :Int) = Iterator.from(2).takeWhile(m => m * m <= n).forall(n % _ != 0) def number(a :List[Int]) = a.foldLeft(0)(_ * 10 + _) def rotate(a :List[Int]) = a.tail ++ List(a.head) def repeat(a :List[Int], n :Int) :Iterator[List[Int]] = if(n == 0) Iterator(Nil) else repeat(a, n - 1).flatMap(x => a.map(_ :: x)) def is_min_rotate(a :List[Int]) = { val front = number(a) val it = Iterator.iterate(a)(rotate).slice(1, a.size).map(number) it.forall(front <=) } def is_circular_prime(a :List[Int]) = Iterator.iterate(a)(rotate).take(a.size).map(number).forall(is_prime) def count_rotate(a :List[Int]) = Iterator.iterate(a)(rotate).take(a.size).toSet.size val N = 6 val it = for(n <- Iterator.range(2, N + 1); a <- repeat(List(1, 3, 7, 9), n) if is_min_rotate(a)) yield a println (it.filter(is_circular_prime).map(count_rotate).sum + 4)
