用Python打印一系列质数

Question

用Python打印一系列质数

35

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

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

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

36个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hochl · Answer 1

你提前终止了循环。在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

正如您所看到的，无需计算平方根，更快的方法是为每个质数存储平方数，并将每个除数与该数字进行比较。

- Arif awate · Answer 2

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

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

- shashank shekhar · Answer 3

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

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

- Soumik Bhattacharya · Answer 4

# 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

- Gayan Chathuranga · Answer 5

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

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.600秒

用户态CPU时间 0m6.532秒

内核态CPU时间 0m0.036秒

- Mirav T. Mehta · Answer 6

2

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)

- Mirav T. Mehta

2

虽然这段代码可能提供了问题的解决方案，但最好添加上为什么/如何运作的上下文。这可以帮助未来的用户学习并最终将该知识应用到他们自己的代码中。当代码被解释时，您还可能会得到用户的积极反馈/赞同。 - Amit Verma

- moldovean · Answer 7

这是一个简单直观的递归函数，用于检查一个数是否为素数！ :) （我在MIT课程的作业中完成了它）在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：

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

在100000以内有9594个质数。

[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秒来计算它。 :)

- srikar kodakandla · Answer 8

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

- Taalib Zama · Answer 9

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函数的简化答案。

- Tortue Genial · Answer 10

我受到Igor的启发，写了一段代码块来创建一个列表：

def prime_number():

for num in range(2, 101):
    prime = True
    for i in range(2, num):
        if (num % i == 0):
            prime = False
    if prime and num not in num_list:
        num_list.append(num)
    else:
        pass
return num_list


num_list = []
prime_number()
print(num_list)