这是我试图解决的问题。
这个数字197被称为圆形素数，因为数字的所有旋转：197,971和719本身都是素数。
在100：2,3,5,7,11,13,17,31,37,71,73,79和97之下有十三个这样的素数。
一百万以下有多少个圆形素数？
这是我的尝试。我首先将所有素数低于1000000放在名为primes的列表中，然后计算所有可能的排列并将这些排列存储在列表中。然后我检查了那些排列是否是素数。
import math
def isPrime(num):
flag = 1
root = int(math.sqrt(num) + 1)
for i in range (2,root+1):
if num%i == 0:
flag = 0
break
else:
flag = 1
if flag == 1:
return True
else:
return False
primes = [#list of all primes below 1000000]
def permutations(word):
if len(word) == 1:
return [word]
char = word[0]
perms = permutations(word[1:])
result = []
for perm in perms:
for i in range (len(perm)+1):
result.append(perm[i:] + char + perm[:i])
return result
count = 0
for i in primes:
to_be_tested = permutations(str(i))
count_to_be_fulfilled = len(to_be_tested)
new_count = 0
for j in to_be_tested:
if isPrime(int(j)):
new_count += 1
if new_count == count_to_be_fulfilled:
count += 1
print(count)
我得到答案22，根据Project Euler，这是错误的。我不知道答案，因为我想自己解决这个问题，不想作弊。请告诉我我做错了什么。
我不会发布完整的解决方案，因为从Project Euler's about部分：
我学到了很多解决问题XXX所以可以在其他地方发布我的解决方案吗？
您似乎已回答了自己的问题。没有什么比这更像“啊哈！”当你终于击败了你已经工作了一段时间的问题的那一刻。通常最好的意图是希望分享我们的见解，以便其他人也能享受这一时刻。然而，可悲的是，对于您的读者来说情况并非如此。真正的学习是一个积极的过程，看到它是如何完成的，距离体验那种发现的顿悟还有很长的路要走。请不要否认别人你有如此丰富的自己的价值。
不过，我会给你一些提示。
正如我在评论中提到的，使用集合将大大提高程序的性能，因为访问这些数据的速度非常快（如果你不了解它，你可以通过谷歌搜索一种叫做哈希的技术来检查它）。确切地说，列表的表现将是O(N)而对于集合，它将是关于O(1)。
在问题陈述中，您需要计算数字的旋转。正如@ottomeister所指出的那样，你应该检查你的程序是否正在执行问题语句期望它做的事情。目前，调用permutations("197")将返回以下列表 - ['791', '917', '179', '971', '719', '197'] - 而问题预计结果为['197', '971', '719']。您应该计算旋转，而不是创建排列，例如可以通过将每个数字向左移动（包裹）直到返回初始数字（如果您真的喜欢那些，可以制作类似递归算法）。
您目前正在检查每个数字是否为素数，方法是执行一个循环，检查N是否可以被sqrt(N)所有的整数整除。正如您所注意到的，对于大量数字而言这是非常缓慢的，并且有更好的方法来检查数字是否为素数。在您的场景中，理想的解决方案是简单地执行N in primes，因为您已经生成了素数，如果您使用集合而不是列表，则将为O(1)。或者，您可以查看primality tests（尤其是启发式和概率测试）
我通常建议在其他一切之前测试你自己的解决方案，你可能很容易发现你的permutations功能根本不符合问题陈述的预期结果。我建议将事情进一步分解为更小的函数，例如你可以有一个类似于你的rotations(number)的permutations函数，也许是is_circular(number)函数，它检查给定的数字是否满足问题要求和count_circular(upper_bound)函数计算和计算循环数。如果您还要随意评论所有内容，它将使调试事项变得更加容易，并且您将能够确认所有内容都按预期运行:)