Python 中的素数生成器

Question

我正在尝试编写一个程序来显示 2 到 50 之间的素数。

def primeNr(interval):
    print("Prime numbers from 2 to ",interval,"/n")

    for i in range(1, interval):
        c=0
        for j in range(1, i):
            if(i%j==0):
                c+=1
        if(c==2):
            print (i)

但是当我调用它时，我得到了错误的输出（4,9,25,49）（

primeNr(50)

） - 我不知道为什么。

作为一个额外的问题 - 如何使以下代码返回包含以下数字的列表，然后假设我想要两个变量 p 和 q 从素数列表中选择一个随机数，例如

p=primeNr(50)
q=primeNr(50)

（是的，它与 RSA 相关）。

Answer 1

range的第二个参数是不包含的，所以你需要执行以下操作：（你可以在这里查看文档：python range的定义）

for j in range(1, i + 1)

在数学上有一些改进的机会，例如，你只需要循环到

math.sqrt

，你第一时间意识到一个数字不是素数，只是中断。 （仍然不是最优化的，要进一步优化，您可以查看各种素筛）。

import math

def primeNr(interval):
    print("Prime numbers from 2 to ", interval)

    #if interval itself should be included, then change this to range(2, interval + 1)
    for i in range(2, interval):
        isPrime = True
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            print(i)

primeNr(50)

以下内容基于 @aryamccarthy 所做的一些建议编辑（感谢您提出这个想法！）。它使用特定的 python 语法 - for...else （当循环正常完成而没有遇到任何中断时执行 else 子句）：

import math

def primeNr(interval):
    print("Prime numbers from 2 to ", interval)

    for i in range(2, interval + 1):
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                break
        else:
            print(i)

primeNr(50)

Answer 2

range

不包括其结束限制。 因此，您正在找到具有三个除数的数字（即素数的平方）。

Answer 3

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;