在python中查找前N个素数
在python中查找前N个素数
提问于 2009-10-27 13:44:35
我是编程领域的新手。我只是用python写了这段代码来生成N个素数。用户应输入N的值，该值是要打印的质数的总数。我已经写了这段代码，但它没有抛出所需的输出。相反，它打印质数，直到第N个数字。
例如:用户输入值N= 7。
期望输出: 2，3，5，7，11，13，19
实际输出: 2，3，5，7
敬请指教。
i = 1
x = int(input("Enter the number:"))
for k in range(1, x+1):
c = 0
for j in range(1, i+1):
a = i % j
if a == 0:
c = c + 1
if c == 2:
print(i)
else:
k = k - 1
i = i + 1回答 30
Stack Overflow用户
发布于 2009-10-27 14:38:27
使用regexp :)
#!/usr/bin/python
import re, sys
def isPrime(n):
# see http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None
N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100 # upper-bound of search space
l = list() # result list
while len(l) < N:
l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
M += 100 # increment upper-bound
print l[:N] # print result list limited to N elementsStack Overflow用户
发布于 2009-10-29 00:31:43
作为参考，不同的解决方案之间存在着非常显著的速度差异。下面是一些比较代码。Lennart指出的解决方案称为“历史性”，Ants提出的解决方案称为"naive"，RC提出的解决方案称为“regexp”。
from sys import argv
from time import time
def prime(i, primes):
for prime in primes:
if not (i == prime or i % prime):
return False
primes.add(i)
return i
def historic(n):
primes = set([2])
i, p = 2, 0
while True:
if prime(i, primes):
p += 1
if p == n:
return primes
i += 1
def naive(n):
from itertools import count, islice
primes = (n for n in count(2) if all(n % d for d in range(2, n)))
return islice(primes, 0, n)
def isPrime(n):
import re
# see http://tinyurl.com/3dbhjv
return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None
def regexp(n):
import sys
N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100 # upper-bound of search space
l = list() # result list
while len(l) < N:
l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
M += 100 # increment upper-bound
return l[:N] # print result list limited to N elements
def dotime(func, n):
print func.__name__
start = time()
print sorted(list(func(n)))
print 'Time in seconds: ' + str(time() - start)
if __name__ == "__main__":
for func in naive, historic, regexp:
dotime(func, int(argv[1]))在我的机器上，当n= 100时，输出结果是：
naive
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
Time in seconds: 0.0219371318817
historic
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
Time in seconds: 0.00515413284302
regexp
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
Time in seconds: 0.0733318328857正如你所看到的，这里有一个很大的差异。这里又是1000 (去掉了主输出)：
naive
Time in seconds: 1.49018788338
historic
Time in seconds: 0.148319005966
regexp
Time in seconds: 29.2350409031Stack Overflow用户
发布于 2010-02-06 19:28:37
由David Eppstein实现的超级快速筛子-在我的PC上，前1000个素数需要0.146秒：
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while True:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
primes = gen_primes()
x = set()
y = 0
a = gen_primes()
while y < 10000:
x |= set([a.next()])
y+=1
print "x contains {:,d} primes".format(len(x))
print "largest is {:,d}".format(sorted(x)[-1])页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1628949
复制相关文章
相似问题
腾讯云开发者
