Python 初学者循环（寻找素数）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14656473/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python Beginner's Loop (Finding Primes)
提问by
I'm truly a beginner at python so I apologise for the lack of knowledge, but the reason I'm asking is that reading the Python manual and tutorial (http://docs.python.org/2.7/tutorial) I'm not unable to totally grasp how loops work. I've written some simple programs so I think I get the basics but for whatever reason this program that is meant to list all primes less than or equal to n is not working:
我真的是 Python 的初学者，所以我为缺乏知识而道歉，但我问的原因是阅读 Python 手册和教程（http://docs.python.org/2.7/tutorial）我是并非无法完全掌握循环的工作原理。我写了一些简单的程序，所以我想我已经掌握了基础知识，但是无论出于何种原因，这个旨在列出所有小于或等于 n 的素数的程序都不起作用：
n = int(raw_input("What number should I go up to? "))
p = 2
while p <= n:
for i in range(2, p):
if p%i == 0:
p=p+1
print "%s" % p,
p=p+1
print "Done"
The output when I enter 100 for example is:
例如，当我输入 100 时的输出是：
2 3 5 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87 89 95 97 101 Done
Which looks almost right but for some reason contains 27, 35, 95, which are composite of course. I've been trying to pick apart the way my loop works but I just don't see where it skips checking for divisibility suddenly. I figured that if someone had a look they could explain to me what about the syntax is causing this. Thanks a bunch!
看起来几乎正确，但由于某种原因包含 27、35、95，当然它们是复合的。我一直在尝试区分我的循环的工作方式，但我只是没有看到它突然跳过检查可分性的地方。我想，如果有人看一眼，他们可以向我解释导致这种情况的语法是什么。谢谢一堆！
采纳答案by Volatility
I would actually restructure the program to look like this:
我实际上会将程序重组为如下所示：
for p in range(2, n+1):
for i in range(2, p):
if p % i == 0:
break
else:
print p,
print 'Done'
This is perhaps a more idiomatic solution (using a forloop instead of a whileloop), and works perfectly.
这可能是一个更惯用的解决方案（使用for循环而不是while循环），并且效果很好。
The outer forloop iterates through all the numbers from 2 to n.
外for循环遍历从 2 到 的所有数字n。
The inner one iterates to all numbers from 2 to p. If it reaches a number that divides evenly into p, then it breaks out of the inner loop.
内部一个迭代到从 2 到 的所有数字p。如果它达到一个能整除 的数p，则它会跳出内部循环。
The elseblock executes every time the for loop isn't broken out of (printing the prime numbers).
该else块每执行（打印素数）的for循环没有爆发的时间。
Then the program prints 'Done'after it finishes.
然后程序'Done'在完成后打印。
As a side note, you only need to iterate through 2 to the square root of p, since each factor has a pair. If you don't get a match there won't be any other factors after the square root, and the number will be prime.
作为旁注，您只需要遍历 2 到 的平方根p，因为每个因子都有一对。如果你没有得到匹配，在平方根之后就不会有任何其他因素，这个数字就是素数。
回答by tacaswell
you do not re-start the iloop after you find a non-prime
i找到非质数后不要重新开始循环
p = i = 2
while p <= n:
i = 2
while i < p:
if p%i == 0:
p += 1
i = 1
i += 1
print p,
p += 1
print "Done"
A whileloop executes the body, and then checks if the condition at the top is True, if it is true, it does the body again. A forloop executes the body once for each item in the iterator.
一个while循环执行的身体，然后检查是否在顶部的情况是True，如果这是真的，它再次增强身体。一个for循环执行体一次迭代器的每个项目。
回答by Guddu
Please compare your snippet with the one pasted below and you will notice where you were wrong.
请将您的代码段与下面粘贴的代码段进行比较，您会发现自己错在哪里。
n = int(raw_input("What number should I go up to? "))
p = 2
while p <= n:
is_prime=True
for i in range(2, p):
if p%i == 0:
is_prime=False
break;
if is_prime==True:
print "%d is a Prime Number\n" % p
p=p+1
回答by Ioannis
Better use
更好的使用
for i in range(2, p//2 + 1):
回答by steveha
Your code has two loops, one inside another. It should help you figure out the code if you replace the inner loop with a function. Then make sure the function is correct and can stand on its own (separate from the outer loop).
您的代码有两个循环，一个在另一个循环中。如果您用函数替换内循环，它应该可以帮助您找出代码。然后确保函数正确并且可以独立存在（与外循环分开）。
Here is my rewrite of your original code. This rewrite works perfectly.
这是我对您原始代码的重写。这种重写工作完美。
def is_prime(n):
i = 2
while i < n:
if n%i == 0:
return False
i += 1
return True
n = int(raw_input("What number should I go up to? "))
p = 2
while p <= n:
if is_prime(p):
print p,
p=p+1
print "Done"
Note that is_prime()doesn't touch the loop index of the outer loop. It is a stand-alone pure function. Incrementing pinside the inner loop was the problem, and this decomposed version doesn't have the problem.
请注意，is_prime()不要触及外循环的循环索引。它是一个独立的纯函数。p在内循环内部递增是问题，而这个分解版本没有问题。
Now we can easily rewrite using forloops and I think the code gets improved:
现在我们可以使用for循环轻松重写，我认为代码得到了改进：
def is_prime(n):
for i in range(2, n):
if n%i == 0:
return False
return True
n = int(raw_input("What number should I go up to? "))
for p in range(2, n+1):
if is_prime(p):
print p,
print "Done"
Note that in Python, range()never includes the upper bound that you pass in. So the inner loop, which checks for < n, we can simply call range(2, n)but for the outer loop, where we want <= n, we need to add one to nso that nwill be included: range(2, n+1)
请注意，在 Python 中，range()从不包括您传入的上限。因此，检查 的内循环< n可以简单地调用，range(2, n)但对于我们想要的外循环<= n，我们需要添加一个，n以便n将其包括在内：range(2, n+1)
Python has some built-in stuff that is fun. You don't need to learn all these tricks right away, but here is another way you can write is_prime():
Python 有一些很有趣的内置东西。您不需要立即学习所有这些技巧，但这里有另一种编写方式is_prime()：
def is_prime(n):
return not any(n%i == 0 for i in range(2, n))
This works just like the forloop version of is_prime(). It sets ito values from range(2, n)and checks each one, and if a test ever fails it stops checking and returns. If it checks nagainst every number in the range and not anyof them divide nevenly, then the number is prime.
这个工程就像for环路版本is_prime()。它设置i值range(2, n)并检查每个值，如果测试失败，它会停止检查并返回。如果它检查n范围内的每个数字，并且没有任何一个被整除n，则该数字是质数。
Again, you don't need to learn all these tricks right away, but I think they are kind of fun when you do learn them.
同样，您不需要立即学习所有这些技巧，但我认为当您学习它们时，它们会很有趣。
回答by mayank
for i in range(2, p):
if p%i == 0:
p=p+1
print "%s" % p,
p=p+1
I am going to tell your error only,in line 3 you are incrimenting p but actually what you are missing is your i if your i in previous case is let say 13 then it will check your loop after 13 but it is leaving 2,3,5,7,11 so its an error .that is what happening in case of 27 your i before 27 is 13 and now it will check from 14.and I don't think u need an solution.
我只会告诉你的错误，在第 3 行你正在增加 p 但实际上你缺少的是你的 i 如果你在前一种情况下的 i 是 13 那么它会在 13 之后检查你的循环，但它会离开 2,3 ,5,7,11 所以它是一个错误。这就是在 27 的情况下发生的情况，你在 27 之前的 i 是 13，现在它将从 14 开始检查。我认为你不需要解决方案。
回答by Adeel
This should work and is bit more optimized
这应该可以工作并且更加优化
import math
for i in range(2, 99):
is_prime = True
for j in range(2, int(math.sqrt(i)+1)):
if i % j == 0:
is_prime = False
if is_prime:
print(i)
回答by John Haggin
def is_prime(n):
if n>=2:
for i in range(2, n):
if n%i == 0:
return False
return True
else:
return False
To find PRIME NUMBER
查找 PRIME 号码
回答by Omid
Let's do a couple more improvements.
让我们再做一些改进。
- You know 2 is the only even prime number, so you add 2 in your list and start from 3 incrementing your number to be checked by 2.
- Once you are past the half-way point (see above
sqrtand*examples), you don't need to test for a prime number. - If you use a list to keep track of the prime numbers, all you need to do is to divide by those prime numbers.
- 您知道 2 是唯一的偶素数，因此您在列表中添加 2，并从 3 开始将您的数字增加 2。
- 一旦你过了中点（见上文
sqrt和*例子），你就不需要测试素数了。 - 如果您使用列表来跟踪质数，您需要做的就是除以这些质数。
I wrote my code and each of the above items would improve my code execution time by about 500%.
我写了我的代码，上面的每一项都会将我的代码执行时间提高大约 500%。
prime_list=[2]
def is_prime(a_num):
for i in prime_list:
div, rem = divmod(a_num, i)
if rem == 0:
return False
elif div < i:
break;
prime_list.append(a_num)
return True
回答by J. Fenech
This in my opinion is a more optimised way. This finds all the prime numbers up to 1,000,000 in less than 8 seconds on my setup.
在我看来，这是一种更优化的方式。在我的设置中，这会在不到 8 秒的时间内找到所有高达 1,000,000 的质数。
It is also one of my very first attempts at python, so I stand to be corrected
这也是我对 python 的第一次尝试之一，所以我会得到纠正
class prime:
def finder (self):
import math
n = long(raw_input("What number should I go up to? "))
for i in range(2, n):
is_prime = True
if i % 2 == 0:
is_prime = False
for j in range(3, long(math.sqrt(i) + 1), 2):
if i % j == 0:
is_prime = False
break
if is_prime:
print(i)
prime().finder()
