The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
可截素数
3797有着奇特的性质。不仅它本身是一个素数，而且如果从左往右逐一截去数字，剩下的仍然都是素数：3797、797、97和7；同样地，如果从右往左逐一截去数字，剩下的也依然都是素数：3797、379、37和3。
只有11个素数，无论从左往右还是从右往左逐一截去数字，剩下的仍然都是素数，求这些数的和。
注意：2、3、5和7不被视为可截素数。
import math
def is_Prime(number):
if number < 2:
return False
for x in range(2, int(math.sqrt(number)) + 1):
if number % x == 0:
return False
return True
def get_children(number):
result = [number]
number_level = len(str(number))
for i in range(1, number_level):
result.append(eval(str(number)[i:]))
result.append(eval(str(number)[:i]))
return result
result = 0
for i in range(8, 739798):
if is_Prime(i) and not '0' in str(i):
ok = True
numbers = get_children(i)
for n in numbers:
if not is_Prime(n):
ok = False
break
if ok:
print i
result += i
print "result = %s" % result
上面一个是比较愚蠢的暴力破解方法，唯二的magic number就是8和739798，最初版本就是题目说了有11个素数嘛，就设了11循环，一开始其实算出来最大的是739397。
[Finished in 12.9s]
下面是这个快很多的一个方法，比较奇怪的就是2的问题，其他就用奇数来拼数字，至少少了一半的计算量
import math
def is_Prime(number):
if number < 2:
return False
for x in range(2, int(math.sqrt(number)) + 1):
if number % x == 0:
return False
return True
def get_children(number):
result = [number]
number_level = len(str(number))
for i in range(1, number_level):
result.append(eval(str(number)[i:]))
result.append(eval(str(number)[:i]))
return result
line = []
for a in [1, 3, 5, 7, 9]:
for b in [1, 3, 5, 7, 9]:
line.append(eval("%s%s" % (b, a)))
for c in [1, 3, 5, 7, 9]:
line.append(eval("%s%s%s" % (c, b, a)))
for d in [1, 3, 5, 7, 9]:
line.append(eval("%s%s%s%s" % (d, c, b, a)))
for e in [1, 3, 5, 7, 9]:
line.append(eval("%s%s%s%s%s" % (e, d, c, b, a)))
for f in [1, 3, 5, 7, 9]:
line.append(eval("%s%s%s%s%s%s" % (f, e, d, c, b, a)))
line.append(eval("%s%s%s%s%s" % (2, d, c, b, a)))
line.append(eval("%s%s%s%s" % (2, c, b, a)))
line.append(eval("%s%s%s" % (2, b, a)))
line.append(eval("%s%s" % (2, a)))
result = 0
for i in line:
if is_Prime(i):
ok = True
numbers = get_children(i)
for n in numbers:
if not is_Prime(n):
ok = False
break
if ok:
print i
result += i
print "result = %s" % result
这个跑下来结果是：
[Finished in 1.2s]
至少还能接受是吧。
我觉得还能直接在素数末尾加数字来弄，应该可以快更多。