我一直在努力解决Project Euler Problem 37(虽然Euler Pro问题的精神是独立求解，但我已经合理地尽了最大努力，认为这个错误可能是语法错误(。无论如何，以下是我的代码(顺便说一句，我很高兴听到任何关于一般改进的建议(：
# 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.
primes = [2, 3, 5, 7, 11, 13]
trun_primes = []
# Tests whether number "n" is a trucatable prime, doesn't test whether "n" is prime itself
def test_trun(n):
trun_versions = []
for d in range(1, len(str(n))):
trun_versions.append(int(str(n)[:len(str(n)) - d]))
for d in range(1, len(str(n))):
trun_versions.append(int(str(n)[d:]))
test = 0
for v in trun_versions:
if v not in primes:
test += 1
if test == 0:
return True
else:
return False
n = primes[len(primes) - 1] + 2
while len(trun_primes) != 11:
ptest = []
for p in primes:
ptest.append(n % p)
if 0 in ptest:
n += 2
else:
primes.append(n)
if test_trun(n) == True:
trun_primes.append(n)
# Debugging tool:
print trun_primes
n += 2
print sum(trun_primes)
每次运行它时，结果都是一样的(除了运行时，我选择结束它(：@JohnCleman，l32是"；ptest.append(n%p("；，然而，这个问题已经得到解决。Atom脚本运行程序
您可以"组装"；通过组合可能的第一位、中间位和最后一位而得到的素数。
第一个数字必须是素数，因为当截断右侧时，它将单独结束
所以第一个数字只能是2、3、5或7
最后一个数字也必须是素数，但它也将是多位数的最后一个必须是素数的数字。所以它不可能是偶数，也不可能是5(以5结尾的数字是5的倍数(
所以最后一个数字只能是3或7
中间位数最终将是素数的最后一位，因此它们不可能是偶数，也不可能是5。
因此中间位数只能是1、3、7或9。
鉴于此，您可以"；构建"；通过组合这些数字并检查它们是素数和可截断的：
def isPrime(N): return all(N%d for d in range(2,int(N**0.5)+1))
def isLeftTrunc(S): return all(isPrime(int(S[i:])) for i in range(len(S)))
def truncablePrimes(prefix=None):
if not prefix:
for p in (2,3,5,7): # first digits (2,3,5,7)
yield from truncablePrimes(p*10) # expand with suffixes
return
for n in (prefix+3,prefix+7): # last digits (3,7)
if isLeftTrunc(str(n)): # return truncables
yield n
for n in (prefix+1,prefix+3,prefix+7,prefix+9): # middle digits (1,3,7,9)
if isPrime(n): # valid right truncable
yield from truncablePrimes(n*10) # expand with suffixes
输出：
print(sorted(truncablePrimes()))
# [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
print(sum(truncablePrimes()))
# 748317
这在0.0000003秒的中运行
据我所知，您的代码应该在足够的时间/计算能力下获得正确的结果。问题是这个程序花了很多时间做不必要的工作。
例如，想想当n非常大但仍然可以被3整除时会发生什么，比如204483。尽管你很快就知道它不可能是素数，但该程序仍在扫描其他数千个素数。
CCD_ 2中也存在类似的低效率。
另一个微妙的慢点是检查v not in primes。由于Python只知道primes是一个未排序的列表，所以这很慢。https://wiki.python.org/moin/TimeComplexity
作为一个欧莱里人，我不能确切地告诉你如何解决它，但你很接近。祝你好运
感谢所有回答的人，您给了我一些想法，在过去的几天里我已经实现了这些想法。我将for循环切换到while循环，它在继续之前检查测试是否已经失败。我在素数搜索中发现了一个错误，因为缺少缩进，每次不是素数时，我的n都会增加4。我还添加了大约15个不同的调试打印命令，其中大多数现在已经被注释掉了。
我还打算创建一个二进制搜索函数，它可以更有效地检查trun_versions[v]是否处于素数，但它在后台运行了大约3分钟后还是找到了答案。
然而，我很困惑，为什么test_trun函数中while循环的第二个条件不要求我从len(trun_version(中减去1，因为列表的索引从0开始，对吧？
# 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.
primes = [2, 3, 5, 7, 11, 13]
trun_primes = []
# Tests whether number "n" is a trucatable prime, doesn't test whether "n" is prime itself
def test_trun(t):
trun_versions = []
for d in range(1, len(str(n))):
trun_versions.append(int(str(t)[:len(str(n)) - d]))
trun_versions.append(int(str(t)[d:]))
# print "TRUN_VERSIONS = " + str(trun_versions)
ttest = 0
v = 0
# NO CLUE why the following line does not function unless v != len(trun_versions) - 1 is replaced by what is there now. Would've thought there would be an index error otherwise.
while ttest == 0 and v != len(trun_versions):
# print "TESTING TRUN_VERSION = " + str(trun_versions[v])
if trun_versions[v] not in primes:
# print "NOT FOUND"
ttest = 1
v += 1
if ttest == 0: #or n != 29 or n != 59 or n != :
# print "TRUN_PRIME"
trun_primes.append(t)
print trun_primes
# print "TRUN_PRIMES = " + str(trun_primes)
return True
else:
# print "NOT TRUN_PRIME"
return False
n = primes[len(primes) - 1] + 2
while len(trun_primes) != 11:
# print "n = " + str(n)
ptest = 1
i = 0
while ptest != 0 and i != len(primes) - 1:
p = primes[i]
# print "p = " + str(p)
ptest = n % p
# print "n % p = " + str(n % p)
i += 1
if ptest == 0:
# print "NOT PRIME"
n += 2
else:
primes.append(n)
# print "PRIME"
# print "PRIMES = " + str(primes)
test_trun(n)
n += 2
# print ""
print sum(trun_primes)
# Answer: 748317
# Truncatable Primes: 23, 37, 53, 73, 313, 317,
# 373, 797, 3137, 3797, 739397