有人可以告诉我这段代码在做什么吗？ 无论如何，它只是打印"计数"。 我只想要一个非常简单的素数生成器(没什么花样)。
1
2
3
4
5
6
7
8
9
10
11
12
13import math
def main():
count = 3
one = 1
while one == 1:
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
continue
if count % x != 0:
print count
count += 1
你可以发表一些输出吗？
它不终止吗？ 毫不奇怪的是其中带有" while = 1："。 它根本不产生任何输出吗？ 它会产生非素数吗？ 太慢了吗？ 不是C＃吗？ 问题是什么？
如果这不是家庭作业，则可能需要研究Eratosthenes筛网：en.wikipedia.org/wiki/Sieve_of_Eratosthenes
我第二个CTT评论。 即使不是那么容易编码，也将同样容易。
有关Eratosthenes筛网的简单实现的信息，请参见：stackoverflow.com/questions/2068372/
有一些问题：
当计数不除以x时，为什么要打印计数？这并不意味着它是素数，仅意味着该特定x不会将其除
continue移至下一个循环迭代-但您确实想使用break停止它
这是您的代码，其中包含一些修复程序，它仅输出质数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17import math
def main():
count = 3
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 1
有关更有效的质子生成，请参见其他人建议的戊二烯筛。这是一个不错的，经过优化的实现，带有很多注释：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/
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
请注意，它返回一个生成器。
这个筛子非常简洁。它从哪里来的？
那是筛子的一个非常好的实施。我以前从未见过它适用于无限范围，但回顾起来很明显。
字典操作非常耗时，如果您有足够的内存，则最好将所有数字保存在内存中，而不要使用字典来动态添加和删除元素。
@xiao我认为"运行中"的时间平均是恒定的，最糟糕的是线性
@yatisagade，嘿，python中的字典实现基于动态的集合，该集合不是laverage常量。它应该是log(n)。
@xiao看看：wiki.python.org/moin/TimeComplexity
要查看此作品，请在people.csail.mit.edu/pgbovine/python/tutor.html#mode=edit上进行尝试
如果您想查看此代码的来源，请参阅此线程code.activestate.com/recipes/117119-sieve-of-eratosthenes，并进行一些改进(在我的测试中为4倍)
确实应该推迟将值添加到dict中，直到在输入中看到它们的平方为止，如在stackoverflow.com/a/10733621/849891中。这大大降低了内存消耗，并改善了增长顺序。 cf.测试条目和相关讨论。
所以等等，如何使用呢？
@FerdinandoRandisi：它返回一个生成器
直到现在都没见过。
这种动态筛子非常酷。为了进行校准，使其能够像这样运行无限发生器，使其比常规静态筛网慢3倍左右，后者将筛网预先填充到sqrt(max_prime)。
而推迟版本的Will Ness链接到一个简单的静态筛网所需的时间约为0.8。
1
2
3
4
5
6
7
8
9
10
11
12
13def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
return False
for x in range(2, num):
if num % x == 0:
return False
else:
return True
>> filter(is_prime, range(1, 20))
[2, 3, 5, 7, 11, 13, 17, 19]
我们将在列表中得到所有质数不超过20的质数。
我本来可以用Eratosthenes的筛子，但是你说
您想要非常简单的东西。 ;)
1不是质数。 2和3是质数，并且丢失。因此，这对于前三个数字已经不起作用。
@heikogerlach非常正确。我已经解决了这个问题。现在请投票给我:)
如果您一直使用数字，它将修改为0并返回false。
其他是不必要的。如果它是素数，则该函数将返回True，并且可能会使初学者感到困惑。
如果将for x in range(2, num)更改为for x in range(2, math.trunc(math.sqrt(num)) + 1)，则会得到相同的结果，但速度更快。
re功能强大：
1
2
3
4
5
6
7
8
9
10import re
def isprime(n):
return re.compile(r'^1?$|^(11+)1+$').match('1' * n) is None
print [x for x in range(100) if isprime(x)]
###########Output#############
[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]
非常聪明！对那些感兴趣的人的解释。
1print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
这很简单，但效率不高。在典型的PC上，它需要几秒钟才能在range(10000)中工作
1
2
3
4
5
6
7def primes(n): # simple Sieve of Eratosthenes
odds = range(3, n+1, 2)
sieve = set(sum([range(q*q, n+1, q+q) for q in odds],[]))
return [2] + [p for p in odds if p not in sieve]
>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
要测试数字是否为质数：
1
2
3
4>>> 541 in primes(541)
True
>>> 543 in primes(543)
False
这是一个简单的(Python 2.6.2)解决方案...与OP的原始请求(现在已经六个月大)保持一致；并且应该是任何"编程101"课程中的一个完全可接受的解决方案。
1
2
3
4
5
6
7
8
9
10
11
12import math
def isPrime(n):
for i in range(2, int(math.sqrt(n)+1)):
if n % i == 0:
return False;
return n>1;
print 2
for n in range(3, 50):
if isPrime(n):
print n
这种简单的"强力"方法"足够快"，足以使现代PC上的数字达到约16,000(在我的2GHz盒子上花费约8秒)。
显然，这可以通过不重新计算每个偶数的素数或每个单个数字的3、5、7等的倍数来更有效地完成……请参见Eratosthenes筛(请参见上述eliben的实现)，甚至是Atkin筛子，如果您感到特别勇敢和/或疯狂。
注意警告：我是python noob。请不要接受我所说的任何福音。
我认为最好是采用功能性方法，
因此，我首先创建一个函数以找出数字是否为质数，然后根据需要在循环或其他位置使用它。
1
2
3
4
5def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
然后运行简单的列表推导或生成器表达式以获取素数列表，
1[x for x in range(1,100) if isprime(x)]
这似乎是作业，所以我将给出提示而不是详细说明。如果我认为做错了，请指正。
当您看到一个偶数除数时，您可以很好地解决问题。
但是，即使您看到一个不除的数字，也要立即打印"计数"。例如，2并不能平均分为9。但这并不能使9成为质数。您可能要继续操作，直到确定范围内没有数字匹配为止。
(正如其他人回答的那样，筛子筛查是一种更有效的方法……只是试图帮助您理解为什么此特定代码没有按照您的意愿做)
如果要直接计算素数，该怎么办：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def oprime(n):
counter = 0
b = 1
if n == 1:
print 2
while counter < n-1:
b = b + 2
for a in range(2,b):
if b % a == 0:
break
else:
counter = counter + 1
if counter == n-1:
print b
另一个简单示例，仅考虑奇数进行简单优化。一切都用惰性流完成(python生成器)。
用法：素数=列表(create_prime_iterator(1，30))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22import math
import itertools
def create_prime_iterator(rfrom, rto):
"""Create iterator of prime numbers in range [rfrom, rto]"""
prefix = [2] if rfrom < 3 and rto > 1 else [] # include 2 if it is in range separately as it is a"weird" case of even prime
odd_rfrom = 3 if rfrom < 3 else make_odd(rfrom) # make rfrom an odd number so that we can skip all even nubers when searching for primes, also skip 1 as a non prime odd number.
odd_numbers = (num for num in xrange(odd_rfrom, rto + 1, 2))
prime_generator = (num for num in odd_numbers if not has_odd_divisor(num))
return itertools.chain(prefix, prime_generator)
def has_odd_divisor(num):
"""Test whether number is evenly divisable by odd divisor."""
maxDivisor = int(math.sqrt(num))
for divisor in xrange(3, maxDivisor + 1, 2):
if num % divisor == 0:
return True
return False
def make_odd(number):
"""Make number odd by adding one to it if it was even, otherwise return it unchanged"""
return number | 1
SymPy是用于符号数学的Python库。它提供了几种生成素数的功能。
1
2
3
4
5
6
7
8
9
10
11isprime(n) # Test if n is a prime number (True) or not (False).
primerange(a, b) # Generate a list of all prime numbers in the range [a, b).
randprime(a, b) # Return a random prime number in the range [a, b).
primepi(n) # Return the number of prime numbers less than or equal to n.
prime(nth) # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1) # Return the largest prime smaller than n
nextprime(n) # Return the ith prime greater than n
sieve.primerange(a, b) # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes.
这里有些例子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18>>> import sympy
>>>
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[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]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[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]
这是Eratosthenes筛子的小巧版本，具有很好的复杂性(比对长度为n的数组排序要低)和矢量化。
1
2
3
4
5
6
7
8import numpy as np
def generate_primes(n):
is_prime = np.ones(n+1,dtype=bool)
is_prime[0:2] = False
for i in range(int(n**0.5)+1):
if is_prime[i]:
is_prime[i*2::i]=False
return np.where(is_prime)[0]
时间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14import time
for i in range(2,10):
timer =time.time()
generate_primes(10**i)
print('n = 10^',i,' time =', round(time.time()-timer,6))
>> n = 10^ 2 time = 5.6e-05
>> n = 10^ 3 time = 6.4e-05
>> n = 10^ 4 time = 0.000114
>> n = 10^ 5 time = 0.000593
>> n = 10^ 6 time = 0.00467
>> n = 10^ 7 time = 0.177758
>> n = 10^ 8 time = 1.701312
>> n = 10^ 9 time = 19.322478
1
2
3
4
5
6
7
8
9
10
11def genPrimes():
primes = [] # primes generated so far
last = 1 # last number tried
while True:
last += 1
for p in primes:
if last % p == 0:
break
else:
primes.append(last)
yield last
我们真的需要测试101除以97，以找出101是否为质数吗？
使用生成器：
1
2
3
4
5
6def primes(num):
if 2 <= num:
yield 2
for i in range(3, num + 1, 2):
if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
yield i
用法：
1
2for i in primes(10):
print(i)
2, 3, 5, 7
继续语句看起来不对。
您想从2开始，因为2是第一个质数。
您可以编写" while True："来获得无限循环。
1
2
3
4
5
6
7
8
9
10def check_prime(x):
if (x < 2):
return 0
elif (x == 2):
return 1
t = range(x)
for i in t[2:]:
if (x % i == 0):
return 0
return 1
您可以以相当优雅的方式使用列表推导来创建素数列表。从这里拍摄：
1
2
3
4>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
这是我所拥有的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def is_prime(num):
if num < 2: return False
elif num < 4: return True
elif not num % 2: return False
elif num < 9: return True
elif not num % 3: return False
else:
for n in range(5, int(math.sqrt(num) + 1), 6):
if not num % n:
return False
elif not num % (n + 2):
return False
return True
对于大数来说，这是非常快的，因为它只针对数字的除数来检查已经存在的质数。
现在，如果要生成素数列表，可以执行以下操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19# primes up to 'max'
def primes_max(max):
yield 2
for n in range(3, max, 2):
if is_prime(n):
yield n
# the first 'count' primes
def primes_count(count):
counter = 0
num = 3
yield 2
while counter < count:
if is_prime(num):
yield num
counter += 1
num += 2
为了提高效率，可能需要在此处使用发电机。
仅供参考，而不是说：
1
2
3one = 1
while one == 1:
# do stuff
您可以简单地说：
1
2while 1:
#do stuff
如果要查找范围内的所有素数，可以执行以下操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
return False
for x in range(2, num):
if num % x == 0:
return False
else:
return True
num = 0
itr = 0
tot = ''
while itr <= 100:
itr = itr + 1
num = num + 1
if is_prime(num) == True:
print(num)
tot = tot + ' ' + str(num)
print(tot)
只需添加while its <=和您的数字作为范围。
输出：
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
您需要确保所有可能的除数不均分您要检查的数字。在这种情况下，只要可能的除数之一没有均匀地除以该数字，您就可以随时打印要检查的数字。
另外，您也不想使用continue语句，因为当您发现数字不是质数时，continue只会使它检查下一个可能的除数。
与user107745类似，但使用'all'而不是双重否定(更具可读性，但我认为性能相同)：
1
2import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
基本上在(2，100)范围内的x上进行迭代，并对范围(2，x)中的所有t只选择那些不具有mod == 0的那些
另一种方法可能是在填充素数时：
1
2
3
4
5
6
7
8
9
10
11
12primes = set()
def isPrime(x):
if x in primes:
return x
for i in primes:
if not x % i:
return None
else:
primes.add(x)
return x
filter(isPrime, range(2,10000))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30import time
maxnum=input("You want the prime number of 1 through....")
n=2
prime=[]
start=time.time()
while n<=maxnum:
d=2.0
pr=True
cntr=0
while d
if n%d==0:
pr=False
else:
break
d=d+1
if cntr==0:
prime.append(n)
#print n
n=n+1
print"Total time:",time.time()-start
对我而言，以下解决方案看起来很简单且易于遵循。
1
2
3
4
5
6
7
8
9
10
11
12import math
def is_prime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num) + 1)):
if num % i == 0:
return False
return True
is_prime(121)==是，但121不是素数。