我在打印从一到一百的一系列素数时遇到了问题。我无法弄清楚我的代码有什么问题。
这是我写的；它打印所有奇数而不是素数：
for num in range(1, 101):
for i in range(2, num):
if num % i == 0:
break
else:
print(num)
break
问问题
258866 次
35 回答
72
您需要检查从 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)
你可以写同样的更短和更 Pythonic：
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)
于 2012-07-23T20:31:02.860 回答
17
两千多年前由希腊数学家埃拉托色尼发明的一种更好的方法不是试除法，而是通过反复抛出多个素数来进行筛选。
首先列出从 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 的平方根处停止。我会把优化的版本留给你处理。
于 2012-07-23T20:57:29.580 回答
15
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
于 2012-07-23T20:25:16.623 回答
15
我支持不假设最佳解决方案并对其进行测试。下面是我所做的一些修改，以通过@igor-chubin 和@user448810 创建简单的示例类。首先让我说这都是很好的信息，谢谢大家。但我必须感谢@user448810 的聪明解决方案，结果证明这是迄今为止最快的（在我测试过的解决方案中）。所以向你致敬，先生！在所有示例中，我使用 100 万 (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 秒
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 秒
注意：上面列出的解决方案 5（由 user448810 提出）结果证明是最快、最安静的创意和聪明的。我喜欢它。多谢你们！！
编辑：哦，顺便说一句，我觉得没有必要为值的平方根导入数学库，因为等价的只是 (n**.5)。否则，我没有进行太多编辑，然后将值存储在输出数组中以由类返回。此外，将结果存储到文件中可能比详细存储更有效，并且如果一次只存储一个文件可以节省大量内存，但由于磁盘写入会花费更多时间。我认为总有改进的余地。所以希望代码有意义。
2021 年编辑：我知道这已经很长时间了，但我在将 Stackoverflow 链接到我的 Codewars 帐户后返回并查看了我最近累积的积分，这些积分与这篇文章相关联。我在原始海报中读到的东西引起了我对@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
将近五年后，我可能知道得更多，但我仍然喜欢 Python，想想它已经这么久了有点疯狂。老实说，这篇文章感觉就像是不久前发表的，当时我想我只使用 python 大约一年。它似乎仍然相关。疯狂的。美好时光。
于 2016-08-23T16:18:52.980 回答
3
解决上述问题的最佳方法是使用“Miller Rabin Primality Test”算法。它使用概率方法来确定一个数字是否为素数。它是迄今为止我遇到过的最有效的算法。
同样的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
于 2016-08-20T05:18:10.590 回答
2
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
于 2013-07-31T03:31:54.613 回答
2
我将素数列出到一个条目数字而没有太多麻烦的方法是使用这个属性，您可以通过素数的总和获得任何不是素数的数字。
因此，如果你用它下面的所有素数来除条目数，并且它不能被它们中的任何一个整除，你就知道你有一个素数。
当然还有更快的获得素数的方法，但是这个已经表现得很好，特别是因为你没有将条目数除以任何数字，而只是将素数一直到那个数字。
使用此代码，我在计算机上设法在不到 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)
于 2015-06-26T18:11:42.763 回答
2
解决这个问题的一种更简单、更有效的方法是存储之前找到的所有素数并检查下一个数字是否是任何较小素数的倍数。
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是一个短路功能，换句话说，一旦找到真值，它将立即中断循环。
于 2018-12-19T14:34:45.103 回答
2
返回第一个 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
于 2016-06-10T06:42:01.967 回答
2
我们可以使用 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)
于 2019-08-21T13:31:40.077 回答
1
# 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
于 2015-03-17T20:34:45.370 回答
1
这是一个简单直观的检查它是否是 RECURSIVE 函数中的素数的版本！:) （我是作为 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 集成的简单 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 秒来计算它。:)
于 2013-10-15T10:43:11.097 回答
1
您过早地终止循环。在你测试了 for 循环体中的所有可能性并且没有中断之后，这个数字就是素数。由于一个不是素数，你必须从 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
如您所见，无需计算平方根，存储每个素数的平方并将每个除数与该数字进行比较会更快。
于 2015-06-19T11:14:16.427 回答
1
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 函数的简化答案。
于 2019-10-24T13:39:29.637 回答
1
除了已接受的答案之外，可以通过使用列表来存储素数并在生成后打印它们来实现进一步的优化。
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
于 2018-02-10T10:05:04.357 回答
1
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)
于 2021-02-26T14:26:00.103 回答
1
这是初学者获取素数的最简单逻辑：
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
于 2018-06-08T06:28:45.953 回答
1
这个怎么样？阅读我使用的所有建议：
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
系统 0m0.036s
于 2016-09-30T09:52:17.787 回答
0
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)
于 2014-09-08T00:43:03.657 回答
0
使用 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,
于 2013-07-04T16:07:49.023 回答
0
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
于 2015-06-19T07:04:02.627 回答
0
这是我编写的一个示例程序，用于检查一个数字是否为素数。
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
于 2015-06-22T19:06:54.213 回答
0
a=int(input('enter the lower no.'))
b=int(input('enter the higher no.'))
print("Prime numbers between",a,"and",b,"are:")
for num in range(a,b):
if num>1:
for i in range(2,num):
if (num%i)==0:
break
else:
print(num)
于 2018-07-14T16:00:21.340 回答
0
这是一种不同的方法，可以用空间换取更快的搜索时间。这可能是最快的。
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
于 2017-10-17T21:11:56.970 回答
0
使用过滤功能。
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
于 2016-08-09T17:53:32.907 回答
0
我受到 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)
于 2018-01-26T11:46:39.587 回答
0
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
于 2016-07-28T08:02:04.010 回答
0
省略素数的最快和最佳实现：
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)
于 2017-10-08T05:57:19.907 回答
0
添加我自己的版本，只是为了展示一些 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
于 2017-05-18T05:42:36.003 回答
0
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
于 2017-07-11T02:28:49.707 回答
0
for i in range(1, 100):
for j in range(2, i):
if i % j == 0:
break
else:
print(i)
于 2021-07-13T04:50:17.890 回答
0
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
于 2016-08-15T17:40:56.000 回答
0
首先我们找到那个数字的因数
def fac(n):
res = []
for i in range(1,n+1):
if n%i == 0:
res.append(i)
检查素数的脚本
def prime(n):
return(fac(n) == [1,n])
打印所有素数到 n 的脚本
def prime_list(n):
pri_list = []
for i in range(1,n+1):
if prime(i)
pri_list.append(i)
return(pri_list)
于 2018-07-24T18:23:25.827 回答
-1
min = int(input("输入下限：")) max = int(input("输入上限："))
print("",min,"和",max,"之间的素数是："
for num in range(min,max + 1): if num > 1: for i in range(2,num): if (num % i) == 0: break else: print(num)
于 2018-12-19T13:31:12.027 回答
-1
num= int(input("Enter the numbner"))
isDivisible= False
int=2
while i<num:
if num%i==0
isDivisible True
print("The number {} is divisible by {}.".format(num,i))
i +=1
if isDivisible:
print("The number {} is not prime.".format(num))
else:
print("The number {} is a prime number.".format(num))
于 2018-05-06T10:06:01.170 回答