在python中寻找低于给定数的所有循环素数。

Question

我需要写一个代码，它可以生成任何给定数字下面的所有循环质数。我的代码有一些缺陷，它并没有提供所有的所有圆质数，只是提供了其中的几个圆质数。例如，如果 upper = 200，它不会显示圆质数 197。其他旋转数是971和719。然而，如果 upper = 1000，它将显示所有 3 个循环质数。我不知道这是否是一个逻辑或代码错误，但任何和所有的帮助是感激的。

from collections import deque
def gen_primes(upper):

    D = {}
    q = 2
    while q <= upper:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]       
        q += 1 

def circular_primes(upper):
    circular = []

    primes = list(gen_primes(upper-1))

    for prime in primes:
        string = str(prime)
        digits = deque(string)

        for rotation in range(1, len(string)):
            digits.rotate(1)

            if int("".join(digits)) not in primes:
                break
        else:
            circular.append(prime)

    return circular
print(circular_primes(150))

Answer 1

代码修复

你没有创建涵盖所有可能的旋转的质数。

增加一个函数，计算大于n的最小数字及其所有的旋转。

def next_largest(n):
  " For number n, returns number smallest number larger than all rotation of n "
  k = len(str(n))

  return 10**k

重构后的代码

from collections import deque
def gen_primes(upper):

    D = {}
    q = 2
    while q <= upper:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]       
        q += 1 

def next_largest(n):
   " For number n, returns number smallest number larger than all rotation of n "
  k = len(str(n))

  return 10**k

def circular_primes(upper):
    circular = []

    print(next_largest(upper))
    primes = list(gen_primes(next_largest(upper)))  # code mod

    for prime in primes:
        string = str(prime)
        digits = deque(string)

        for rotation in range(1, len(string)):
            digits.rotate(1)

            if int("".join(digits)) not in primes:
                break
        else:
            circular.append(prime)

    return circular

测试

print(circular_primes(200))

产量

[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991]