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

范围的第二个参数不包括在内,因此您需要执行以下操作:(您可以在此处查看文档:python范围的定义)

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)