数素数，其旋转都是素数

Question

此代码解决了欧拉项目问题35：

这个数字197被称为圆形素数，因为数字197、971和719的所有旋转本身都是素数。有13个这样的素数低于100: 2，3，5，7，11，13，17，31，37，71，73，79和97。在一百万以下有多少个圆形素数？

from collections import deque

def sieve(limit):
    nums = [True] * (limit+1)
    nums[0] = nums[1] = False

    for i, is_prime in enumerate(nums):
        if is_prime:
            yield i
            for n in range(i*i, limit+1, i):
                nums[n] = False

def rotations(n):
    l = deque(list(str(n)))
    r = []

    for _ in range(len(l)):
        r.append(int("".join(list(l))))
        l.rotate()
    return r

def circular_prime(n):
    cp = []
    s = list(sieve(n))
    for i in s:
        r = rotations(i)
        flags = [False] * len(r)
        for k, j in enumerate(r):
            if j in s:
                flags[k] = True
        if all(flags):
            print(i)
            cp.append(i)
    return len(cp)


print(circular_prime(1000000))

我怎样才能加快速度？如果我用标准Python解释器运行它，需要花费太长时间。但是，通过在"pypy“解释器中运行，我可以将执行时间缩短到13秒。

Answer 1

不要检查是否有偶数数字

添加

if n<10:
    return [n]
if any(even in str(n) for even in "02468"):
    return []

进入rotations，因为每个数字(除了2)和最后一个偶数数都不是素数，所以没有必要为这些数字生成旋转。

避免过度转换

l = deque(str(n)) -不需要list转换也可以检查字符串片-您可以只使用它们进行旋转，而不是使用deque。

在迭代集合时避免更改它，

for i, is_prime in enumerate(nums):
    ...
            nums[n] = False

是不好的。把它重构

使用列表理解

flags变量显然是一团糟。让我看看..。

    flags = [False] * len(r)
    for k, j in enumerate(r):
        flags[k] = j in s #True for True, False for False
    if all(flags):

好的，现在把它移到标志的初始化中。

    flags = [j in s for k,j in enumerate(r)]
    if all(flags):

不需要k。旗帜也是：

    if all(j in s for j in r):

这看起来更好，工作更快-因为它停止后，第一个错误。但现在我们不需要：

    if all(j in s for j in rotations(i)):

现在您可以重写rotations以使用yield而不是创建列表。这样会快得多。

不要将筛子转换成列表

你白白浪费时间和记忆。用筛子工作，而不是单子。在筛子中搜索将是O(1)，而不是O(n) (if s[j]而不是if j in s)。for i循环现在将超过整个范围(2.n)，跳过如果不是s我。

Answer 2

免责声明:这篇评论将提到对您的代码的改进，这些改进可能是由其他答案提供的。最后，我将提出一个完全不同的算法来解决这个问题。

更好地使用筛网

使用筛子是个好主意，特别是因为我们对我们感兴趣的值有一个已知的上限。然而，从筛子到列表的转换使它的使用速度变慢:它使得所有其他质数检查都很昂贵，因为需要在列表中执行线性搜索。一个更快的选择是按原样使用它:数组映射号到它们的素数。

在实践中，您只需要从return nums函数中提取筛子，然后：

def circular_prime(n):
    cp = []
    s = sieve(n)
    for i, is_prime in enumerate(s):
        if is_prime:
            r = rotations(i)
            flags = [False] * len(r)
            for k, j in enumerate(r):
                if s[j]:
                    flags[k] = True
            if all(flags):
                print(i)
                cp.append(i)
    return len(cp)

这种简单的改变会带来巨大的性能改进。

旗

涉及标志的逻辑可以简化很多，并且是：if all(s[j] for j in rotations(i)):。

执行较小数量的素测试

对于找到的每一个循环数，我们检查它的所有旋转。最终，所有的数字都被检查了很多次。另一种策略可能是检查我们正在考虑的数字是否是其轮调中最小的。如果它是，如果它确实是一个循环素数，那么它的所有旋转都可以同时加入到结果中。

            r = set(rotations(i))
            if i == min(r) and all(s[j] for j in r):
                print(r)
                cp.extend(r)

一种不同的算法

对于我们正在寻找的数字(大于9)，可以进行一些数学观察：

• 素数(大于9)不会以0、2、4、6、8或5结尾。这将导致最后一个数字为1、3、7、9。
• 因此，循环素数不会包含这些数字中的任何一个，因为它们将对应于旋转的最后一个数字。圆形素数仅为1、3、7和9的置换。

我们可以通过查找这些排列来限制搜索空间:当考虑具有n位数的数字时，您将只考虑4个ⁿ数，而不是10ⁿ(例如，当n=6时，它会使100000和4096之间的差别)。

我们得到的东西是：

def circular_prime(nb_dig_max):
    cp = [2, 3, 5, 7]
    final_numbers = {'1', '3', '7', '9'}
    s = sieve(10 ** nb_dig_max)
    for l in range(2, nb_dig_max + 1):
        for p in itertools.product(final_numbers, repeat=l):
            p_int = int(''.join(p))
            perm = set(rotations(p_int))
            if p_int == min(perm) and all(s[n] for n in perm):
                cp.extend(perm)
    return len(cp)

在这一阶段，我们将质数检查的数量限制在如此小的数目上，以至于使用筛子的性能不会比简单的素数检查函数更好：

def is_prime(n):
    """Checks if a number is prime."""
    if n < 2:
        return False
    return all(n % i for i in range(2, int(math.sqrt(n)) + 1))


def circular_prime(nb_dig_max):
    cp = [2, 3, 5, 7]
    final_numbers = {'1', '3', '7', '9'}
    for l in range(2, nb_dig_max + 1):
        for p in itertools.product(final_numbers, repeat=l):
            p_int = int(''.join(p))
            perm = set(rotations(p_int))
            if p_int == min(perm) and all(is_prime(n) for n in perm):
                cp.extend(perm)
    return len(cp)

Answer 3

以循环素数197,719,971为例。到达197时，当前代码将检查两个轮值719和971，以确定它们是否为素数。当达到719时，对971和197进行测试。但我们已经知道，这三个数字是循环素数，从他们第一次测试。因此，当只需要前两次时，代码正在执行6次轮转和检查。对于一个6位数的圆形质数，它将是30圈而不是5圈。

这里有一些代码(未经测试)来展示这个想法。

def count_circular_primes(n):
    count = 0
    primes = list(sieve(n))

    for prime in primes:
        r = rotations(prime)

        # if they are circular primes, count them
        if all(primes[i] for i in r):
            count += len(r)

        # mark all the rotations as done
        for i in r:
            primes[i] = False

    return count