うーん、数学的な工夫をあまり思いつかなかったのだが、とりあえず効果のあった高速化は次の2つ。 - 計算の上限を設定。これは、計算してみればわかるが明らかに 6 * 9^5 である。各桁の5乗の和というのは、どうがんばっても6桁のこの数以上にはならないこと…

C言語でまともに配列とかで作業しちゃったら面倒なことになるんだろうけど、まぁ･･･ね。 #!/usr/bin/python seq = set() for a in range(2,101): for b in range(2,101): seq.add(a**b) print len(seq)

これは、図を見てえいやっと考えれば簡単。 #!/usr/bin/python EDGE_MAX = 1001 a,b,c,d = 3,5,7,9 s = 1 diff = 10 while b-a+1 <= EDGE_MAX: s += a + b + c + d edge = b - a + 2 a += diff diff += 8 b = a + edge c = b + edge d = c + edge print s

数学的にいくつか工夫をすると、だいぶ探索数が減らせる。 二次式にn=0を代入すれば、そもそもb自身が素数でであることはすぐにわかる。 n=bの時は式全体はbの倍数である。よって、どんなにがんばってもn=b-1までしか連続した素数は得られない。よって、n=b…