使用Python计算素数

Question

enter code here

所以我开始学习python（python3）并且我得到了这个用于打印素数的程序 这是我的代码：

a=int(input("Enter starting number"))
b=int(input("Enter the ending number"))
while(a!=b):
    for n in range(2, a-1):
        c=a%n
        if(c!=0):
            print(a)

        elif(c==0):
            break
    a+=1

我确实意识到代码对于找出素数是错误的，因为它会打印一些数字，如 9、15、21...这些不是素数，但请先听我说完。

我运行了程序并将值保留为 a=4 b=7

我期望的输出是： 5 5 5 7 7 7 7 7

我得到的答案是： 5 5

我无法理解此输出背后的原因。

我可以获得输出的解释吗？

Answer 1

第一个问题是在循环中，range(2,a-1)不包括最后一个值。如果将其更改为 range(2,a)，则包含您想要的最后一个值，但它不包含 a 的值。然后将打印 5 5 5。要显示 7，请查看 While 循环的逻辑。循环表示，当 a 不等于 b 时，执行循环中的操作。因此，一旦 a = b，循环将不再运行。您希望循环运行直到等于 b，最后运行一次，然后退出。因此，您需要将其更改为 while a != b+1。这将得到您期望的输出。这是更改后的代码。

a=int(input("Enter starting number"))
b=int(input("Enter the ending number"))
while(a!=b+1):
    for n in range(2, a):
        c=a%n
        if(c!=0):
            print(a)

        elif(c==0):
            break
    a+=1

Answer 2

fermets 公式是最简单的一种，但由于使用幂计算，可能会存在内存效率问题（除平方根法和 AKS 法外）

def prime(n):
    # you can replace the 2 with any coprime number
    if (n < 2): return False;
    if 2**(n-1)%(n) == 1: return True;
    return False

def range_primes(r):
    p = [2];
    for i in range(1, r):
        if prime(i) == True:
            p.append(i);
    return p;