Python初学者循环（查找质数）

Question

我是一名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"

当我输入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

这个代码看起来基本正确，但是却包含了27、35、95这些合数数字。我一直在尝试分析我的循环方式，但是我不知道它为什么会突然跳过检查可除性的步骤。我认为如果有人看一眼代码，就可以解释一下语法上的问题所在。非常感谢！

- user2034140

---

PS：我已经成功编写了一个使用for循环而不是while循环实现相同功能的程序。我只是想深入理解这个过程，所以并不是在寻求关于不同方法的建议（尽管如果你有一些好的见解，我也很乐意听取！） - user2034140

不是for循环有问题-算法有问题。你有在纸上尝试过执行吗？如果它给出了相同的（错误）结果，那么你理解循环的方式正确，但算法是错的。 - loopbackbee

@goncalopp 嗯，我觉得算法在纸上是没问题的：至少如果我在纸上执行的内容和我用Python写的一样的话。例如当p被推进到27时，i循环应该会发现当i循环到3时p是可被3整除的，然后p应该向前循环到28。你能帮我理解我理解和我所写的代码之间的差异吗？ - user2034140

@LevLivnev，然后您开始检查28是否可被4整除，所以i变成5，您检查29是否可被5整除，但您从未检查小于5的数字。 - tacaswell

Answer 1

我实际上会重构程序，使其看起来像这样：

for p in range(2, n+1):
    for i in range(2, p):
        if p % i == 0:
            break
    else:
        print p,
print 'Done'

这可能是一种更惯用的解决方案（使用for循环而不是while循环），并且完美运行。

外部的for循环迭代从2到n的所有数字。

内部for循环迭代从2到p的所有数字。如果它找到一个可以整除p的数字，那么它会跳出内部循环。

else块在每次未跳出循环时执行（打印素数）。

然后程序在完成后打印 'Done'。

另外，你只需要迭代2到p的平方根，因为每个因子都有一对。如果你没有找到匹配项，在平方根之后就不会有其他因子了，这个数就是质数。

- Volatility

---

谢谢，这很简单。一开始我尝试使用for循环，但我不知道else也可以用于循环的另一种方式（在循环耗尽后执行），这正是这里所必需的。 - user2034140

Answer 2

你的代码有两个循环，一个在另一个内部。如果你用一个函数替换内部循环，那么它应该帮助你弄清楚代码。然后确保这个函数是正确的并且可以独立于外部循环（即与外部循环分离）。

以下是我对你原始代码的重写。这次重写完美地工作了。

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"

请注意，is_prime() 不会影响外循环的索引。它是一个独立的纯函数。在内部循环中递增 p 是问题所在，而这个分解版本没有这个问题。

现在我们可以轻松地使用 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"

请注意，在Python中，range()从不包括您传递的上限。因此，内部循环检查<n，我们可以简单地调用range(2，n)，但对于外部循环，我们希望<= n ，我们需要将n加一，以便包括n：range(2，n + 1) Python有一些内置的有趣东西。您不需要立即学习所有这些技巧，但是这里是另一种编写is_prime()的方法：

def is_prime(n):
    return not any(n%i == 0 for i in range(2, n))

这个函数的工作方式就像是 for 循环版本的 is_prime()。它将 i 设置为从 range(2, n) 中获取的值，并检查每个值，如果有一个测试失败，它就停止检查并返回。如果它检查了范围内的每个数字与 n 相比较，且没有一个数可以整除 n，那么这个数就是质数。

同样地，你不需要立即学习所有这些技巧，但当你学会它们时，它们会变得有趣。

- steveha

---

这是一种普遍的经验法则：将代码拆分成有用的函数，调试这些函数，然后你就可以依靠这些函数。最好的函数只做一件事情，并且足够简单，让你清楚地理解它们的功能、工作方式和正确性。 - steveha

Answer 3

这应该可以正常工作，并且更加优化。

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)

- Adeel

Answer 4

在找到非质数后，您不需要重新启动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"

一个while循环执行其主体，然后检查顶部的条件是否为True，如果是真的，则再次执行主体。一个for循环对迭代器中的每个项目执行一次主体。

- tacaswell

---

你是说在找到一个非质数并设置p=p+1之后，我需要做类似于continue的操作吗？ 我尝试在后面加上continue，但没有任何变化。您能否详细解释一下为什么i循环不会重新启动？ - user2034140

@LevLivnev：在脑海中逐步执行它。想象一下，你从 p=25 开始。所以，你执行 for i in range(2, p)。当 i 到达 5 时，它可以被 25 整除，因此你执行 p = p + 1。现在 p=26……然后你继续执行 i=6。它不能被 26 整除，所以你继续执行 7、8、9、10、11、12、13。当它到达 14 时，它可以被 26 整除，因此 p = p + 1，现在 p=27，并且它尝试了 14 到 26，其中没有一个能够整除 27，因此 27 是质数。 - abarnert

@tcaswell: +1。但可能只需要进行较小的更改，肯定会更可读，一旦发现p不是质数，就退出for循环，而不是尝试在两个不同的地方递增p和i。（缺点是明显的Pythonic方法是一个for:/ else:，这往往会让初学者感到困惑...） - abarnert

@abarnert 发现非素数并前进到 p+1 后跳出 for 循环正是我希望做的，但放置一个 break 并没有达到我希望的效果。现在我明白了问题所在，但如果不重构代码，我该如何在发现非素数后重置 i 循环呢？ - user2034140

最后我意识到我想要做的是在for:循环之后使用else:，这意味着如果for:循环耗尽，则执行。感谢您的帮助，我认为我现在正在取得一些进展。 - user2034140

Answer 5

请将您的代码片段与下面粘贴的代码进行比较，您会注意到自己哪里出错了。

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

- Guddu

---

你的缩进混乱不堪。哪些语句应该放在哪里？ - abarnert

缩进在从编辑器复制到这里时出了问题...现在已经纠正过来了。 - Guddu

Answer 6

def findprime(num):
  count = 0
  for i in range(1,num+1):
    list1 = []
    for ch in range(1,i+1):
      if i%1==0 and i%ch==0:
        list1.append(ch)
    if len(list1)==2:
      count += 1
      print(i,end=", ")
  print()
  return count  
num2 = int(input("enter a number: "))
result=findprime(num2)
print("prime numbers between 1 and",num2,"are",result)

- brilliant

Answer 7

这是一个更详细的示例，考虑到 Python 3 的优化。

import sys

inner_loop_iterations: int = 0

def is_prime(n):
    a: int = 2
    global inner_loop_iterations

    if n == 1:
        return("Not prime")
    elif n == 2:
        return("Prime")

    while a * a <= n + 1:
        inner_loop_iterations += 1
        # This if statement reduces the number of inner loop iterations by roughy 50%
        # just weeding out the even numbers.
        if a % 2 == 0:
            a += 1
        else:
            a += 2

        if n % 2 == 0 or n % a == 0:
            return ("Not prime")
    else:
        return ("Prime")

while True:
    sys.stdout.write("Enter number to see if it's prime ('q' to quit): ")
    n = input()
    if not n:
        continue
    if n == 'q':
        break

    try:
        n = int(n)
    except ValueError:
        print("Please enter a valid number")

    if n < 1:
        print("Please enter a valid number")
        continue

    sys.stdout.write("{}\n".format(is_prime(n)))
    sys.stderr.write("Inner loops: {}\n\n".format(inner_loop_iterations))
    inner_loop_iterations=0

这个程序有两个主要的优化，首先它只迭代从2到n的平方根，并且只迭代奇数。使用这些优化，我能够发现数字1000000007仅在15811次循环迭代中是质数。

- Sonny Parlin

Answer 8

在我看来，这是一种更优化的方式。在我的设置上，它可以在不到8秒的时间内找到所有小于1,000,000的质数。

这也是我对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()

- J. Fenech

---

问题是关于如何正确地构建for循环，而不是优化。对于您的代码，一些建议：您不应该将函数放在类中，这是不必要的。只需将其单独放在模块中即可。此外，您应该将导入语句放在模块的顶部，而不是函数内部。您应该分离输入、计算和输出：首先询问用户数字，然后有一个函数，它接受一个数字并返回一个布尔值，指示它是否为质数，最后打印该函数的结果。 - user2124834

Answer 9

print('Enter a Number: ')
number=abs(int(input()))
my_List=[0,1]
def is_prime(n):
    if n in my_List:
        return True
    elif n>=2:
        for i in range(2, n):
            if n%i == 0:
                return False
        return True
    else:
        return False

if is_prime(number):
    print("%d is Prime!"%number)
else:
    print(number,'is not prime')

- Ahsanul kabir

Answer 10

for i in range(2, p):
    if p%i == 0:
        p=p+1 
     print "%s" % p,
     p=p+1

我只会告诉你错误，第3行中你正在增加p，但实际上你缺少的是i。如果在先前的情况下，你的i是13，那么它将在13之后检查你的循环，但它会留下2、3、5、7、11，所以这是一个错误。这就是在27的情况下发生的事情，你在27之前的i是13，现在它将从14开始检查。我认为你不需要解决方案。

- mayank