用Python打印一系列质数

Question

我在打印从一到一百的质数时遇到了问题。 我无法弄清楚我的代码有什么问题。

这是我写的代码; 它打印所有奇数而不是质数:

for num in range(1, 101):
    for i in range(2, num):
        if num % i == 0:
            break
        else:
            print(num)
            break

- user1546721

---

可能是列出小于N的所有质数的最快方法的重复问题。 - Ciro Santilli OurBigBook.com

is_prime = lambda n: all( n%i != 0 for i in range(2, int(n**.5)+1) ) - Zaz

Answer 1

您需要检查从2到n-1（实际上是sqrt(n)，但没关系，让它变成n）的所有数字。如果 n 可以被其中任何一个数字整除，那么它就不是质数。如果一个数字是质数，则打印它。

for num in range(2,101):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num)

你可以写成更短、更Pythonic的代码：

for num in range(2,101):
    if all(num%i!=0 for i in range(2,num)):
       print (num)

正如我之前所说的，最好的方法是检查因子不是从2到n-1，而是从2到sqrt(n):

import math
for num in range(2,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print (num)

对于像101这样的小数，这并不重要，但对于10 ** 8来说，差异将非常大。

通过将您检查的范围增加2，从而仅检查奇数，可以进一步改进它。就像这样：

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print (num)

编辑：

由于在第一个循环中选择了奇数，因此在第二个循环中不需要用偶数进行检查，所以“i”值可以从3开始，并每次跳过2。

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
        print (num)

- Igor Chubin

---

干得好，但是为什么你忽略了数字1？ 1不被视为质数。请看这篇文章 https://primes.utm.edu/notes/faq/one.html - Mouneer

将您的range(1,101)更改为range(2,101)，代码就会完美无缺。我们不要忘记1不是质数。 - Akash Adhikari

不需要 import math。只需使用 **.5。 - Zaz

另外，计算平方根是很耗费资源的。比较平方数会更好。 - hochl

你可以通过不为每个“num”计算所有因子来加快速度。如果我们查看“非Pythonic”的代码，并在prime = False之后立即放置break，那么循环将在找到单个因子时停止。在我的实验中，这使得代码运行速度提高了一倍。 - Waqas Ilyas

Answer 2

我主张不要假设最佳解决方案并测试它。以下是我对@igor-chubin和@user448810创建简单示例类的一些修改。首先让我说这是很棒的信息，谢谢你们。但是我必须承认@user448810的聪明解决方案，结果远远是最快的（在我测试的那些中）。所以向你致敬，先生！在所有示例中，我使用1百万（1,000,000）作为n的值。

请随意尝试代码。

祝好运！

方法1由Igor Chubin描述：

def primes_method1(n):
    out = list()
    for num in range(1, n+1):
        prime = True
        for i in range(2, num):
            if (num % i == 0):
                prime = False
        if prime:
            out.append(num)
    return out

基准测试：超过272秒

方法2：由Igor Chubin描述：

def primes_method2(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, num)):
            out.append(num)
    return out

基准测试: 73.3420000076秒

第三种方法，由Igor Chubin描述：

def primes_method3(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out

基准测试：11.3580000401秒

第四种方法，由Igor Chubin描述：

def primes_method4(n):
    out = list()
    out.append(2)
    for num in range(3, n+1, 2):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out

基准测试：8.7009999752秒

方法5：由用户448810描述（我认为相当聪明）：

def primes_method5(n):
    out = list()
    sieve = [True] * (n+1)
    for p in range(2, n+1):
        if (sieve[p]):
            out.append(p)
            for i in range(p, n+1, p):
                sieve[i] = False
    return out

基准测试: 1.12000012398 秒

注释: 上面列出的第5个解决方案（由用户448810提出）被证明是最快的，而且非常有创意和聪明。我喜欢它。谢谢大家！

编辑: 另外，我认为没有必要导入math库来获取值的平方根，因为等价物只是(n**.5)。否则，我没有做太多编辑，只是使值存储在输出数组中并由类返回。另外，将结果存储到文件中可能会更有效率，而且如果一次只处理一个结果，可以节省很多内存，但会花费更多的时间进行磁盘写入。我认为总有改进的空间。希望代码对大家有所帮助。

---

2021 年编辑: 我知道已经过了很长一段时间，但我在将我的Stackoverflow链接到我的Codewars账户后，看到了我的最近累积的分数，这与此贴文相关。我注意到原始作者的一些评论，于是我决定进行轻微修改，即在将输出数组附加之前过滤掉奇数值。这样可以优化，并在Python 3.8的最新版本下获得更好的性能，对于n为1000000，结果为0.723秒（之前的代码）与0.504秒。

def primes_method5(n):
    out = list()
    sieve = [True] * (n+1)
    for p in range(2, n+1):
        if (sieve[p] and sieve[p]%2==1):
            out.append(p)
            for i in range(p, n+1, p):
                sieve[i] = False
    return out

近五年过去了，我可能知道的更多一些，但我仍然热爱Python。想到已经这么长时间了感觉有点不可思议。这篇文章实际上感觉像是在短时间前写的，在那时候我只使用Python大约一年时间。而且它似乎仍然很相关。太疯狂了，好时光。

- jacktrader

---

我对if语句中的两个表达式很好奇，它们不是做同样的事情吗？True % 2始终等于1，那么这不是在检查bool两次吗？ - Manny Fleurmond

我的错误。你是正确的，我认为我在检查值是否存在，而不是返回值，这两种情况下都是布尔值。但出于记录的目的，我不确定更新不正确的代码是否值得，但是很好地发现了问题，然后该行就可以像上面那样简化为“if sieve[p]:”（因此真正的优化只是Python本身，但显然也取决于系统本身）。 - jacktrader

事先已知每隔一个迭代应该跳过，并且每个迭代都检查条件不太快。通过初始化out = list([2])并将循环改为for p in range(3, n+1, 2):，我能进一步提高运行时间。对于n=10^6和1000次迭代，我发现每次迭代都进行检查的平均运行时间为0.087秒，而使用增量为2时的运行时间为0.066秒。因此，速度提升了约24%。对于n=10**8的单次迭代，我得到了大约25%的改进结果，因此这似乎是一个有意义的改进。 - xtr

Answer 3

与试除法不同，希腊数学家埃拉托斯特尼发明了一种更好的方法——通过反复排除质数的倍数进行筛选，这一方法已有两千多年历史。

首先从2到所需的最大质数n列出所有数字。然后重复选择最小未被划去的数字，并划去其所有的倍数；剩下的未被划去的数字即为质数。

例如，考虑小于30的数。开始时，2被确认为质数，然后划去4、6、8、10、12、14、16、18、20、22、24、26、28和30。接下来，3被确认为质数，然后划去6、9、12、15、18、21、24、27和30。下一个质数是5，所以划去10、15、20、25和30等数字。如此继续下去，剩余的数字就是质数：2、3、5、7、11、13、17、19、23和29。

def primes(n):
  sieve = [True] * (n+1)
  for p in range(2, n+1):
    if (sieve[p]):
      print p
      for i in range(p, n+1, p):
        sieve[i] = False

一个优化过的埃拉托色尼筛法先单独处理数字2，然后只筛选奇数。另外，由于小于当前素数平方的所有合数都被较小的素数排除了，所以内部循环可以从p^2开始而不是p，外部循环可以停止在n的平方根处。我将让您自己处理优化版本。

- user448810

---

筛法的性能相当差，我怀疑它比尝试除法要快，特别是如果你只尝试到平方根。 - hochl

@hochl 你错了；请看primesieve.org以获取反例。 - Will Ness

哇，我不知道这个，但它非常复杂，使用了多个核心... O.o 但很有趣，谢谢！ :) - hochl

@hochl：它不必很复杂。使用我上面讨论过的筛法的优化版本，计算一百万以内的质数只需要三分之一秒钟。而使用相应的试除法则需要超过二十倍的时间。代码在ideone.com/5U2Wns。primesieve.org上的代码更加复杂，但速度仍然更快。 - user448810

不错！内存需求很大，但如果你开始计算质数，那可能不是问题。我的质数生成器比简单的试除法要快得多，但仍然慢了约6倍（200万次：筛选0.5，简单迭代13.2，生成器3.76）。 - hochl

@hochl：你可以使用位(bit)代替字节(byte)，将内存需求降低8倍，同时你可以使用分段筛法(segmented sieve)，将内存需求从_n_降低到sqrt(n)。 - user448810

Answer 4

break语句会结束当前所在的循环。因此，你只能检查它是否被2整除，从而得到所有的奇数。

for num in range(2,101):
    for i in range(2,num):
        if (num%i==0):
            break
    else:
        print(num)

话虽如此，有比这种方法更好的途径在Python中找到质数。

for num in range(2,101):
    if is_prime(num):
        print(num)

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

- Rob Wagner

---

这是Python文档中描述break/continue的页面，其中包括打印质数的示例！http://docs.python.org/tutorial/controlflow.html（第4.4节） - kaveman

不，你错了。当然，continue在这里没有帮助。如果你认为自己是对的，请用continue编写解决方案。 - Igor Chubin

Answer 5

最好的解决上述问题的方法是使用 "Miller Rabin Primality Test" 算法。它使用概率方法来判断一个数字是否为质数。这是我目前发现的最有效的算法。 下面演示了该算法的Python实现：

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See https://dev59.com/v2w15IYBdhLWcg3w6f80
    # for justification

    # If number is even, it's a composite number

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in xrange(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in xrange(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

- Azharullah Shariff

Answer 6

我的素数列表方法不会让你烦恼，因为你可以用质数的总和获取任何非素数。

因此，如果您将输入数字除以所有小于它的质数，并且不能被其中任何一个整除，那么您知道您有一个质数。

当然，仍然有更快的获取质数的方法，但是这种方法已经表现得相当出色，特别是因为你只需要将质数一直除到达到该数字，而不是除以任何数字来获取输入数字的素数。

使用此代码，在我的计算机上不到4秒钟即可列出100,000以下的所有素数。

import time as t

start = t.clock()

primes = [2,3,5,7]

for num in xrange(3,100000,2):
    if all(num%x != 0 for x in primes):
        primes.append(num)

print primes
print t.clock() - start
print sum(primes)

- user3604362

Answer 7

一个Python程序的函数模块，用于返回前N个质数：

def get_primes(count):
    """
        Return the 1st count prime integers.
    """
    result = []
    x=2
    while len(result) in range(count):
        i=2
        flag=0
        for i in range(2,x):
            if x%i == 0:
                flag+=1
                break
            i=i+1
        if flag == 0:
            result.append(x)
        x+=1
    pass
    return result

- M.K.DHEERAJ

Answer 8

Igor Chubin的回答可以改进。 当测试X是否为质数时，算法不必检查每个小于X平方根的数字，它只需要检查所有小于sqrt(X)的质数。 因此，如果在创建列表时参考质数列表，算法会更有效率。 下面的函数输出所有小于b的质数列表，这样作为一个列表是很方便的（例如，当你想知道小于b的质数数量时）。 只检查质数可以节省更高数字的时间（比较约在10,000左右; 差异显著）。

from math import sqrt
def lp(b)
    primes = [2]
    for c in range(3,b):
        e = round(sqrt(c)) + 1
        for d in primes:
            if d <= e and c%d == 0:
                break
        else:
            primes.extend([c])
    return primes

- user2636407

---

这是低效的：对于一个质数候选者，这将访问所有先前的质数（并测试它们是否满足 d <= e）。在达到平方根后，循环应该总是被打破。 - Will Ness

或者完全删除sqrt，因为它是一项昂贵的操作，而是比较平方，即for d in primes: if d*d > c: ... - hochl

Answer 9

更简单、更高效的解决方法是存储之前发现的所有质数，并检查下一个数是否是较小质数的倍数。

n = 1000
primes = [2]

for i in range(3, n, 2):
    if not any(i % prime == 0 for prime in primes):
        primes.append(i)

print(primes)

请注意，any是一种短路函数，换句话说，只要找到一个真值，就会中断循环。

- Carlos Afonso

---

我不确定为什么，但我测试了这个实现的运行时间，结果比jacktrader发布的解决方案慢了数百倍。虽然有可能是我在测试中犯了错误，但我建议在使用这个实现时要小心谨慎。 - xtr

Answer 10

我们可以使用sympy库来制作质数列表。

import sympy
lower=int(input("lower value:"))          #let it be 30
upper=int(input("upper value:"))          #let it be 60
l=list(sympy.primerange(lower,upper+1))   #[31,37,41,43,47,53,59]
print(l)

- praveen nani