在python中打印素数系列

问题描述：

我在打印一系列从 1 到 100 的素数时遇到了问题。我不知道我的代码出了什么问题。

这是我写的；它打印所有奇数而不是质数：

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

解决方案 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)

你可以写出更短、更 Python 风格的代码：

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)

解决方案 2：

我主张不要假设最佳解决方案并对其进行测试。以下是我为创建简单示例类所做的一些修改，这些修改均由 @igor-chubin 和 @user448810 提供。首先，我要说这些都是很棒的信息，谢谢大家。但我必须感谢 @user448810 的巧妙解决方案，事实证明这是迄今为止最快的解决方案（在我测试过的解决方案中）。所以，向您致敬，先生！在所有示例中，我都使用 1 百万（1,000,000）作为 n。

Igor Chubin 描述的方法 1 ：

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 秒

Igor Chubin 描述的方法 2 ：

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 描述的方法 3 ：

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 描述的方法 4 ：

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 秒

用户448810 描述的方法5 （我认为非常聪明）：

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（由 user448810 提出）被证明是速度最快、最有创意和最聪明的方案。我喜欢它。谢谢大家！！

哦，顺便说一句，我觉得没有必要导入用于计算某个值的平方根的数学库，因为等价的只是 (n**.5)。除此之外，我没有做太多编辑，只是将值存储在输出数组中，以供类返回。此外，将结果存储到文件中可能比详细存储更有效率，如果一次只存储一个，可以节省大量内存，但由于磁盘写入，会花费更多时间。不过，我认为总有改进的空间。

我在原始发帖人中读到的一些东西引起了 @user448810 的注意，所以我决定对原始帖子中提到的内容进行一些小修改，在附加输出数组之前过滤掉奇数值。结果显示，无论是优化还是最新版本的 Python 3.8，其性能都好得多，结果为 0.723 秒（先前的代码），而使用 1,000,000 作为 n 时则为 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

解决方案 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 的平方根处停止。我将优化版留给您自己研究。

解决方案 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

解决方案 5：

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

解决方案 6：

解决上述问题的最佳方法是使用“Miller Rabin 素数测试”算法。它使用概率方法来判断某个数字是否为素数。它是迄今为止我遇到的最有效的算法。

其 Python 实现如下所示：

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # 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

解决方案 7：

返回前 N 个素数的 Python 程序函数模块：

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

解决方案 8：

解决这个问题的一个更简单、更有效的方法是存储之前找到的所有素数，并检查下一个数字是否是任何较小素数的倍数。

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是一个短路函数，换句话说，一旦找到真值，它就会中断循环。

解决方案 9：

我们可以使用 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)

解决方案 10：

我不用太多麻烦就将质数列为一个条目数字的方法是利用以下属性：您可以通过质数的乘积得到任何非质数的数字。

因此，如果用该数字除以其下面的所有质数，并且它不能被其中任何一个整除，则说明该数字是一个质数。

当然，还有更快的方法来获取素数，但是这个方法已经表现得相当好了，特别是因为你没有用任何数字除以输入数字，而是只用素数一直除到该数字。

利用此代码，我能够在不到 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)

解决方案 11：

这是一个简单而直观的版本，用于检查它是否为递归函数中的素数！:)（我把它作为麻省理工学院课程的家庭作业）在 python 中，它运行速度非常快，直到 1900 年。如果你尝试超过 1900，你会得到一个有趣的错误:)（你想检查你的计算机可以管理多少个数字吗？）

def is_prime(n, div=2):

    if div> n/2.0: return True

    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)

#The program:
until = 1000
for i in range(until):
    if is_prime(i):
        print i

当然……如果您喜欢递归函数，可以使用字典升级此小代码，以大大提高其性能，并避免出现那个有趣的错误。这是一个带有 MEMORY 集成的简单 1 级升级：

import datetime
def is_prime(n, div=2):
    global primelist
    if div> n/2.0: return True
    if div < primelist[0]:
        div = primelist[0]
        for x in primelist:
            if x ==0 or x==1: continue
            if n % x == 0:
                return False
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
    if is_prime(i):
        primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."

finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"

这是结果，我打印了找到的最后 100 个素数。

时间日期：2013-10-15 13:32:11.674448

质数有 9594 个，直到 100000

[99991、99989、99971、99961、99929、99923、99907、99901、99881、99877、99871、99859、99839、99833、99829、99823、 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719, 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643、99623、99611、 99607、99581、99577、99571、99563、99559、99551、99529、99527、99523、99497、99487、99469、99439、99431、99409、 99401、99397、99391、99377、99371、99367、99349、99347、99317、99289、99277、99259、99257、99251、99241、99233、 99223、99191、99181、 99173、99149、99139、99137、99133、99131、99119、99109、99103、99089、99083、99079、99053、99041、99023、99017、 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 98929, 98927, 98911, 98909, 98899, 98897] ...

你的计算机花了 0:00:40.871083 来计算

所以我的 i7 笔记本电脑花了 40 秒来计算。:)

解决方案 12：

# computes first n prime numbers
def primes(n=1):
    from math import sqrt
    count = 1
    plist = [2]
    c = 3
    if n <= 0 :
        return "Error : integer n not >= 0"
    while (count <= n - 1):    # n - 1 since 2 is already in plist
        pivot = int(sqrt(c))
        for i in plist:
            if i > pivot :    # check for primae factors 'till sqrt c
                count+= 1
                plist.append(c)
                break
            elif c % i == 0 :
                break    # not prime, no need to iterate anymore
            else :
                continue 
        c += 2    # skipping even numbers              
    return plist

解决方案 13：

您过早终止了循环。在您测试了 for 循环主体中的所有可能性并且没有中断之后，该数字就是素数。由于 1 不是素数，因此您必须从 2 开始：

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

在更快的解决方案中，您只需尝试除以小于或等于您正在测试的数字的根的素数。这可以通过记住您已经找到的所有素数来实现。此外，您只需测试奇数（2 除外）。您可以将生成的算法放入生成器中，以便您可以使用它将素数存储在容器中或简单地将它们打印出来：

def primes(limit):
    if limit > 1:
        primes_found = [(2, 4)]
        yield 2
        for n in xrange(3, limit + 1, 2):
            for p, ps in primes_found:
                if ps > n:
                    primes_found.append((n, n * n))
                    yield n
                    break
                else:
                    if not n % p:
                        break

for i in primes(101):
    print i

如您所见，不需要计算平方根，存储每个素数的平方并将每个除数与该数字进行比较会更快。

解决方案 14：

这个怎么样？阅读完所有建议后，我使用了以下方法：

prime=[2]+[num for num in xrange(3,m+1,2) if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1))]

1000000 以内的质数

root@nfs:/pywork# time python prime.py

78498

实际 0m6.600s

用户 0m6.532秒

系统 0分0.036秒

解决方案 15：

除了可以接受的答案之外，还可以通过使用列表来存储素数并在生成后打印它们来实现进一步的优化。

import math
Primes_Upto = 101
Primes = [2]
for num in range(3,Primes_Upto,2):
    if all(num%i!=0 for i in Primes):
       Primes.append(num)
for i in Primes:
    print i

解决方案 16：

以下是初学者获取素数的最简单的逻辑：

p=[]
for n in range(2,50):
    for k in range(2,50):
        if n%k ==0 and n !=k:
            break
        else:
            for t in p:
                if  n%t ==0:
                    break
            else:
                p.append(n)

print p

解决方案 17：

n = int(input())
is_prime = lambda n: all( n%i != 0 for i in range(2, int(n**.5)+1) )
def Prime_series(n):
    for i in range(2,n):
        if is_prime(i) == True:
            print(i,end = " ")
        else:
            pass
Prime_series(n)

以下是使用 lambda 函数的简化答案。

解决方案 18：

def function(number):
    for j in range(2, number+1):
        if all(j % i != 0 for i in range(2, j)):
            print(j)


function(13)

解决方案 19：

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

解决方案 20：

使用python打印n个素数：

num = input('get the value:')
for i in range(2,num+1):
    count = 0
    for j in range(2,i):
        if i%j != 0:
            count += 1
    if count == i-2:
        print i,

解决方案 21：

def prime_number(a):
    yes=[]
    for i in range (2,100):
        if (i==2 or i==3 or i==5 or i==7) or (i%2!=0 and i%3!=0 and i%5!=0 and i%7!=0 and i%(i**(float(0.5)))!=0):
            yes=yes+[i]
    print (yes)

解决方案 22：

min=int(input("min:"))
max=int(input("max:"))
for num in range(min,max):
    for x in range(2,num):
        if(num%x==0 and num!=1):
            break
        else:
            print(num,"is prime")
            break

解决方案 23：

这是我编写的一个用于检查数字是否为质数的示例程序。

def is_prime(x):
    y=0
    if x<=1:
        return False
    elif x == 2:
        return True
    elif x%2==0:
        return False
    else:
        root = int(x**.5)+2
        for i in xrange (2,root):
            if x%i==0:
                return False
                y=1
        if y==0:
            return True

解决方案 24：

n = int(raw_input('Enter the integer range to find prime no :'))
p = 2
while p<n:
  i = p
  cnt = 0
  while i>1:
    if p%i == 0:
        cnt+=1
    i-=1
  if cnt == 1:
     print "%s is Prime Number"%p
  else:
     print "%s is Not Prime Number"%p
  p+=1

解决方案 25：

使用过滤功能。

l=range(1,101)
for i in range(2,10): # for i in range(x,y), here y should be around or <= sqrt(101)
    l = filter(lambda x: x==i or x%i, l)

print l

解决方案 26：

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

解决方案 27：

f=0
sum=0
for i in range(1,101):
    for j in range(1,i+1):
        if(i%j==0):
            f=f+1
    if(f==2):
        sum=sum+i
        print i        
    f=0
print sum

解决方案 28：

省略素数的最快和最佳实现：

def PrimeRanges2(a, b):
    arr = range(a, b+1)
    up = int(math.sqrt(b)) + 1
    for d in range(2, up):
        arr = omit_multi(arr, d)

解决方案 29：

这是另一种方法，用空间换取更快的搜索时间。这可能是最快的。

import math

def primes(n):
    if n < 2:
        return []
    numbers = [0]*(n+1)
    primes = [2]
    # Mark all odd numbers as maybe prime, leave evens marked composite.
    for i in xrange(3, n+1, 2):
        numbers[i] = 1

    sqn = int(math.sqrt(n))
    # Starting with 3, look at each odd number.
    for i in xrange(3, len(numbers), 2):
        # Skip if composite.
        if numbers[i] == 0:
            continue
        # Number is prime.  Would have been marked as composite if there were
        # any smaller prime factors already examined.
        primes.append(i)
        if i > sqn:
            # All remaining odd numbers not marked composite must be prime.
            primes.extend([i for i in xrange(i+2, len(numbers), 2)
                           if numbers[i]])
            break
        # Mark all multiples of the prime as composite.  Check odd multiples.
        for r in xrange(i*i, len(numbers), i*2):
            numbers[r] = 0

    return primes

n = 1000000
p = primes(n)
print "Found", len(p), "primes <=", n

解决方案 30：

添加我自己的版本，只是为了展示一些 itertools 技巧 v2.7：

import itertools

def Primes():
    primes = []
    a = 2
    while True:
        if all(itertools.imap(lambda p : a % p, primes)):
            yield a
            primes.append(a)
        a += 1

# Print the first 100 primes
for _, p in itertools.izip(xrange(100), Primes()):
    print p