Python - 查找循环质数

Question

我正在尝试找到给定限制下的循环质数数量。prime(x)函数将返回一个数字是否为质数的结果。rotations()函数将返回一个旋转后的数字列表。最后，prime_count()函数将根据给定限制输出循环质数的总数。prime()和rotations()都给出了正确的输出；然而，prime_count()没有像应该一样递增。你有什么想法是我做错了什么吗？

def prime(number): #return true or false
    return all(number% i for i in range(2,number))

def rotations(num): #rotating number and return list
    list = []
    m = str(num)
    counter = 0 
    while counter < len(str(num)):
        m=m[1:] + m[0]
        list.append(int(m))
        counter+=1
    list1=sorted(list,key=int)
    return list1

def prime_count(limit): #return numbers of circular primes from given limit
    counter = 0 

    for i in range(1,limit+1):
        a=rotations(i)
        for j in a:
            if j == prime(j): 
                counter+=1 

    return counter

print(prime_count(100))

- begincoding123

---

你尝试在 prime_count 中打印任何内容以查看其中的变量/数据吗？ - wwii

考虑一下如果你的初始数字包含数字8会发生什么。至少有一个旋转数字是什么，你能说出来吗？你可以对其他数字做出同样的观察，这将帮助你减少需要进行素数测试的数量。 - rossum

Answer 1

您的代码存在几个问题：

1. Your prime function has a bug:

   In [8]: prime(1)
   Out[8]: True
   

   It erroneously returns True for any number less than 2 due to range(2, n) being empty and any([]) == True.

2. prime_count should be counting the total number of circular primes below limit. prime(j) returns a boolean, but you check j == prime(j), which can only be true if j is zero or one, which definitely isn't what you want. Try creating an is_circular_prime function that takes in an integer n and returns whether or not the prime is circular. Then, prime_count becomes easy to write.

- Blender

Answer 2

这是问题的核心：

a=rotations(i)
for j in a:
    if j == prime(j): 
        counter+=1

你正在计算错误的内容（例如，13独立计数两次，而31计数两次），并且在比较错误的内容（数字与布尔值）。问题比你想象的要简单。重新排列您的代码：

def prime(number):
    return number > 1 and all(number % i != 0 for i in range(2, number))

def rotations(num):
    rotated = []

    m = str(num)

    for _ in m:
        rotated.append(int(m))
        m = m[1:] + m[0]

    return rotated

def prime_count(limit):
    counter = 0 

    for number in range(1, limit + 1):

        if all(prime(rotation) for rotation in rotations(number)): 
            counter += 1 

    return counter

print(prime_count(100))

请注意，您不需要为此目的对旋转进行排序。另外，list或任何其他Python内置函数都不是变量的好名称。

- cdlane

Answer 3

问题可能出在这里：

 for i in range(1,limit+1):
        a=rotations(i)
        for j in a:
            if j == prime(j):   # Prime will return True or False, comapring with J will cause it False ,except when J = 1 
                counter+=1 

将其更改为prime(j)

- Rehan Azher

Answer 4

    for i in range(2,number//2):
        if(number%i==0):
            return False 
    return True  

def rotations(num):
    count=0 
    rotation_lst=[]
    num=str(num)
    while(count<len(num)):
        num=num[1:]+num[0]
        count+=1 
        rotation_lst.append(int(num))
    rotation_lst1=sorted(rotation_lst,key=int)
    return rotation_lst1

def get_circular_prime_count(limit):
    count=0
    for i in range(1,limit+1):
        a=rotations(i)

        for j in a:
            if(check_prime(j)):
                count+=1 
    return count 
print(get_circular_prime_count(1000) ```

- Shiva Ariveni