前回のコードでは、197,971,719の素数判定を3回ずつしていることになります。これを避けるには、この3つの中で最も小さい数、すなわちここでは197のみ回転して素数判定をすればよいでしょう。
しかし、回転して最も小さい数だけを生成するのはかなり面倒です。例えば、6桁の数を生成すると考えます。使われる数字の最小を1として、6桁を分割します。最大6分割できますが、ここでは
1のみ|3,7,9|1のみ|3,7,9
の4つの部分に分けます。1のみの部分の桁数が一番左が最も大きければ、問題なく回転して最小です。一番左と同じ部分がある場合は、その右同士を比べます。一番左が一番小さければ回転して最小です。ここで比べるときには、左の桁から順に比べます。375は5より小さいことになります。そして、circular primeであることが分かったら、回転して異なる整数がいくつあるか求めます。ここは個々には時間がかかってもよいのでsetを使えばよいでしょう。
と思ったのですが、よくよく考えると、この考え方ではダメです。例えば、131713とか、1313171317とか。仕方がないので、3,7,9の部分で一番左と同じものがあれば回転してチェックをする、という方法を取りました。これでも十分速いです。107までで前回の方法よりエラトステネスのふるいの部分を除き3倍以上速くなりました。実は、この問題ではPythonがエラトステネスのふるいが遅いこともあり、素数判定は6で割って1か5余る数で次々と割っていくほうがかなり速いです。これだと1桁以上速度が違いました。
ちなみに、106〜1010にcircular primeはありませんでした。
from itertools import product, takewhiledef gen_prime_candidates():
yield 2
yield 3
n = 5
while True:
n += 2
yield n
n += 4
yield ndef is_prime(n):
for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):
if n % p == 0:
return False
return Truedef next(n, m):
return n / m + n % m * 10def gen_cycle(n):
m = 10
num_digits = 1
while m < n:
m *= 10
num_digits += 1
m /= 10
yield n
for k in range(num_digits - 1):
n = next(n, m)
yield ndef is_circular_prime(n):
# print n
for m in gen_cycle(n):
if not is_prime(m):
return False
return Truedef is_smallest_in_circle(n):
for m in gen_cycle(n):
if m < n:
return False
return Truedef is_ascending(a):
prev = a[0]
for k in range(1, len(a)):
n = a[k]
if prev < n:
return True
elif prev > n:
return False
return Truedef gen_decending(a, k = 0, l = 0):
if l == 0:
l = a[k]
if k == len(a):
yield ()
else:
for n in range(1, min(l, a[k]) + 1):
for b in gen_decending(a, k + 1, n if k == 0 else l):
yield (n,) + bdef gen_div_decending(n, m, k = 0):
if m == 1:
if k == 0 or n <= k:
yield (n,)
else:
end = n - m + 2 if k == 0 else min(k + 1, n - m + 2)
for l in range(1, end):
for a in gen_div_decending(n - l, m - 1, max(l, k)):
yield (l,) + adef gen_division(n, m):
if m == 1:
yield (n,)
else:
for l in range(1, n - m + 2):
for a in gen_division(n - l, m - 1):
yield (l,) + a# 1, 3 -> 111
def same_digit_number(d, l):
return reduce(lambda x, y: x * 10 + d, range(l - 1), d)# 1, (3, 2) -> (111, 11)
def make_tuple(d, b):
return sum(map(lambda l: (same_digit_number(d, l),), b), ())def gen_numbers_core(a, d0):
for d in range(d0, 9):
for b in gen_decending(a):
c = make_tuple(d, b)
if is_ascending(a):
yield tuple(map(lambda n: (9,) * n))def tuple_greater(d):
if d == 1: return (3, 7, 9)
elif d == 3: return (7, 9)
elif d == 7: return (9,)
else : return ()def tuple_greater_equal(d):
if d == 1: return (1, 3, 7, 9)
elif d == 3: return (3, 7, 9)
elif d == 7: return (7, 9)
else : return (9,)def gen_greater_number(left_num, size, d0, equal = True):
if equal:
if size == 1:
if size <= len(left_num):
d1 = left_num[0]
for d2 in tuple_greater_equal(d1):
yield (d2,), d1 == d2
else:
for d2 in tuple_greater(d1):
yield (d2,), False
elif len(left_num) == 1:
for d in tuple_greater(left_num[0]):
for a, b in gen_greater_number((), size - 1, d0, False):
yield (d,) + a, False
else:
for d in tuple_greater_equal(left_num[0]):
b = d == left_num[0]
for a, b2 in gen_greater_number(left_num[1:], size - 1, d0, b):
yield (d,) + a, b2
else:
for c in product(tuple_greater(d0), repeat = size):
yield c, Falsedef gen_right_side(a, b, d, k = 0, left_num = 0):
if k == len(a):
yield (), False
elif k == 0:
for c in product(tuple_greater(d), repeat = b[k]):
for t, b1 in gen_right_side(a, b, d, k + 1, c):
yield (c,) + t, b1
elif a[k] < a[0]:
for c in product(tuple_greater(d), repeat = b[k]):
for t, b1 in gen_right_side(a, b, d, k + 1, left_num):
yield (c,) + t, b1
else:
for c, b1 in gen_greater_number(left_num, b[k], d):
for t, b2 in gen_right_side(a, b, d, k + 1, left_num):
yield (c,) + t, b1 or b2def gen_numbers_core(k, d): # k : num of digits, d : num of divisions
for m in range(d, k - d + 1): # num of left digits
for a, b in product(gen_div_decending(m, d), gen_division(k - m, d)):
for d1 in (1, 3, 7, 9):
for c, b1 in gen_right_side(a, b, d1):
r = ()
for p, q in zip(a, c):
r = r + (d1,) * p + q
n = reduce(lambda x, y: x * 10 + y, r)
if not b1 or is_smallest_in_circle(n):
yield ndef gen_numbers():
for n in filter(is_prime, range(2, 10)):
yield n
for k in range(2, M + 1): # number of digits
yield (10 ** k - 1) / 9
for d in range(1, k / 2 + 1): # number of divisions
for n in gen_numbers_core(k, d):
yield ndef unique_number(n):
return len(set(gen_cycle(n)))M = 6
N = 10 ** M
print sum(map(unique_number, filter(is_circular_prime, gen_numbers())))
