python - 圆素数计划欧拉#35

Question

这就是我要解决的问题。

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 以下的所有素数放入一个名为 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，根据欧拉计划，这是错误的。我不知道答案，因为我想自己解决这个问题并且不想作弊。请告诉我我做错了什么。

Answer 1

解决方案

我不会不会发布完整的解决方案，因为来自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")将返回以下列表 - ['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)计算和计算循环数的函数。如果您还对所有内容进行评论，这将使调试变得更加容易，并且您将能够随时确认一切都按预期工作:)