Circular Primes 欧拉计划 #35
Circular Primes Project Euler #35
这是我要解决的问题。
The number, 197, is called a circular prime because all rotations of
the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31,
37, 71, 73, 79, and 97.
How many circular primes are there below one million?
这是我的尝试。我首先将所有低于 1000000 的素数放在一个名为素数的列表中，然后计算它们所有可能的排列并将这些排列存储在一个列表中。然后我检查了这些排列是否是素数。
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，根据欧拉计划，这是错误的。我不知道答案，因为我想自己解决这个问题，不想作弊。请告诉我我做错了什么。
解决方案
我不是post完整的解决方案，因为从Project Euler's about部分：
I learned so much solving problem XXX so is it okay to publish my
solution elsewhere?
It appears that you have answered your own
question. There is nothing quite like that "Aha!" moment when you
finally beat a problem which you have been working on for some time.
It is often through the best of intentions in wishing to share our
insights so that others can enjoy that moment too. Sadly, however,
that will not be the case for your readers. Real learning is an active
process and seeing how it is done is a long way from experiencing that
epiphany of discovery. Please do not deny others what you have so
richly valued yourself.
不过，我会给你一些提示。
数据结构
正如我在评论中提到的那样，使用集合会大大提高程序的性能，因为访问其中的数据非常快（您可以通过谷歌搜索一种称为 散列的技术来检查原因 如果你不知道）。准确地说，列表的性能将是 O(N)，而集合的性能大约是 O(1).
旋转与排列
在问题陈述中，你需要计算一个数的旋转。正如@ottomeister 所指出的，您应该真正检查您的程序是否正在执行问题陈述所期望的操作。目前，调用 permutations("197") 将 return 以下列表 - ['791', '917', '179', '971', '719', '197'] - 而问题预期结果为 ['197', '971', '719']。与其创建 排列 ，不如计算 旋转 ，这可以通过将每个数字向左移动（环绕）直到初始数字是 returned（如果你真的喜欢的话，可以制作这样的递归算法）。
素数检查
您当前正在通过执行一个循环来检查每个数字是否为素数，该循环检查数字 N 是否可以被 sqrt(N) 以内的所有数整除。正如您所注意到的，这对于很多数字来说非常慢，并且有更好的方法来检查数字是否为质数。在你的场景中，理想的解决方案是简单地做 N in primes 因为你已经生成了素数，如果你使用集合而不是列表，它将是 O(1)。或者，您可以查看 primality tests（尤其是启发式和概率测试）
终于
我通常建议先 测试 你自己的解决方案，你很容易发现你的 permutations 函数根本不符合问题陈述的预期结果。我建议将事情进一步分解成更小的函数，例如你可以有一个类似于你的 permutations 的 rotations(number) 函数，也许是一个 is_circular(number) 函数来检查给定的数字是否满足问题要求和 count_circular(upper_bound) 计算和计算循环数的函数。如果您还边走边评论所有内容，这将使调试事情变得容易得多，并且您将能够在旅途中确认一切都按预期工作:)
这是我要解决的问题。
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
这是我的尝试。我首先将所有低于 1000000 的素数放在一个名为素数的列表中，然后计算它们所有可能的排列并将这些排列存储在一个列表中。然后我检查了这些排列是否是素数。
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，根据欧拉计划，这是错误的。我不知道答案，因为我想自己解决这个问题，不想作弊。请告诉我我做错了什么。
解决方案
我不是post完整的解决方案，因为从Project Euler's about部分：
I learned so much solving problem XXX so is it okay to publish my solution elsewhere?
It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.
不过，我会给你一些提示。
数据结构
正如我在评论中提到的那样，使用集合会大大提高程序的性能，因为访问其中的数据非常快（您可以通过谷歌搜索一种称为 散列的技术来检查原因 如果你不知道）。准确地说，列表的性能将是 O(N)，而集合的性能大约是 O(1).
旋转与排列
在问题陈述中，你需要计算一个数的旋转。正如@ottomeister 所指出的，您应该真正检查您的程序是否正在执行问题陈述所期望的操作。目前，调用 permutations("197") 将 return 以下列表 - ['791', '917', '179', '971', '719', '197'] - 而问题预期结果为 ['197', '971', '719']。与其创建 排列 ，不如计算 旋转 ，这可以通过将每个数字向左移动（环绕）直到初始数字是 returned（如果你真的喜欢的话，可以制作这样的递归算法）。
素数检查
您当前正在通过执行一个循环来检查每个数字是否为素数，该循环检查数字 N 是否可以被 sqrt(N) 以内的所有数整除。正如您所注意到的，这对于很多数字来说非常慢，并且有更好的方法来检查数字是否为质数。在你的场景中，理想的解决方案是简单地做 N in primes 因为你已经生成了素数，如果你使用集合而不是列表，它将是 O(1)。或者，您可以查看 primality tests（尤其是启发式和概率测试）
终于
我通常建议先 测试 你自己的解决方案，你很容易发现你的 permutations 函数根本不符合问题陈述的预期结果。我建议将事情进一步分解成更小的函数，例如你可以有一个类似于你的 permutations 的 rotations(number) 函数，也许是一个 is_circular(number) 函数来检查给定的数字是否满足问题要求和 count_circular(upper_bound) 计算和计算循环数的函数。如果您还边走边评论所有内容，这将使调试事情变得容易得多，并且您将能够在旅途中确认一切都按预期工作:)