在Python中打印一系列素数
我正在学习Python编程，而且我很新。
我在印刷从一个到一百个素数的问题时遇到了问题。 我无法弄清楚我的代码有什么问题。
这是我写的。 它打印所有的奇数而不是素数：
for num in range(1,101): for i in range(2,num): if (num%i==0): break else: print(num) break 你需要检查从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
你可以写同样更短，更pyathonic：
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
break了目前的循环。所以，你只能检查它是否可以被2整除，给你所有的奇数。
for num in range(2,101): for i in range(2,num): if (num%i==0): break else: print(num)
也就是说，有更好的方法来findpython的素数比这个更好。
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
希腊math家Eratosthenes在两千年前发明了一种更好的方法，而不是试行分工，而是通过反复剔除多个素数来进行筛选。
首先列出从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的平方根处。 我将离开优化的版本，供您使用。
我是一个没有采取最好的解决scheme和testing它的支持者。 以下是我通过@ igor-chubin和@ user448810创build简单类示例的一些修改。 首先让我说这是所有伟大的信息，谢谢你们。 但是我不得不承认@ user448810他的聪明的解决scheme，这是迄今为止最快的（我testing过的）。 所以对你很好，先生！ 在所有的例子中，我使用100万（100万）的值作为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秒
方法3如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秒
方法4如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秒
如user448810所描述的方法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秒
注意：上面列出的解决scheme5（由user448810提出）certificate是最快和最廉洁的创意和聪明。 我喜欢它。 多谢你们！！
编辑：哦，顺便说一下，我不觉得有什么需要导入math库的平方根的价值，因为相当于（n **。5）。 否则，我没有编辑太多，然后使值存储在和输出数组由类返回。 另外，将结果存储到一个文件可能比冗长一些，如果一次只有一个，可以节省很多内存，但由于磁盘写入会花费更多的时间。 我认为总有改善的余地。 所以希望代码有意义的人。
解决上述问题的最好方法是使用“Miller Rabin Primality Test”algorithm。 它使用概率方法来查找数字是否为素数。 这是迄今为止我所遇到的最有效的algorithm。
下面演示了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
一个Python程序function模块，返回1'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
我把素数上市的方法没有太多的麻烦，就是使用这个属性，你可以得到任何不是质数总和的数字。
因此，如果将所有素数都低于它的条目数除以它们中的任何一个，那么就知道你有一个素数。
当然，还有更快的获得素数的方法，但是这个方法已经performance得相当好了，尤其是因为你并没有用任何数字来区分进入号码，而只是一直到这个数字。
有了这个代码，我在我的计算机上pipe理，在不到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)
使用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,
Igor Chubin的答案可以改善。 当testingX是否为素数时，algorithm不必检查每个数字，直到X的平方根，只需检查直到sqrt（X）的素数。 因此，如果在创build质数时引用质数列表，效率会更高。 下面的函数输出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
这里有一个简单而直观的版本来检查它是否是RECURSIVE函数的主要元素。 :)（我做了一个麻省理工学院课程的作业）在python中运行速度非常快，直到1900年。如果你尝试超过1900，你会得到一个有趣的错误:)（你想检查多less数字电脑可以pipe理？）
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
当然，如果你喜欢recursion函数，这个小代码可以升级一个字典，以严重增加其性能，并避免这个有趣的错误。 这是一个简单的1级升级与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个素数。
时间和date：2013-10-15 13：32：11.674448
有9594个素数，直到100000
[99991,99989,99971,999961,999929,99923,999907,999901,999881,99877,99871,999859,99839,99833,99829,99823,99817,99809,99793,99787,98767,999761,99733,99721,99919 ，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秒来计算它。 🙂
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)
# 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
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
你正在过早地终止循环。 在for循环的主体中testing了所有可能性之后，如果不中断，那么这个数字就是素数。 由于一个不是素数，你必须从2开始：
for num in xrange(2, 101): for i in range(2,num): if not num % i: break else: print num
在一个更快的解决scheme中，您只能尝试用小于或等于您testing的数字的根的素数进行除法。 这可以通过记住所有已经find的素数来实现。 此外，你只需要testing奇数（2除外）。 您可以将生成的algorithm放入一个生成器中，以便您可以使用它将素数存储在容器中，或者直接打印出来：
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
正如你所看到的，没有必要计算平方根，每个素数存储平方的速度更快，每个除数与这个数相比较。
这是我写的一个样例程序，用来检查一个数是否为素数。
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
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
使用filterfunction。
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
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
这个怎么样？ 阅读我使用的所有build议：
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.532s
sys 0m0.036s
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 if=0 print sum
省略素数的最快和最好的实现：
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)
换一种方式来换取更快的search时间。 这可能是最快的。
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
添加我自己的版本，只是为了展示一些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
