0

我知道它已经讨论过很多次了；我读过它，但不知怎的，我无法得到它。我想编写一个程序来确定输入的数字是否为素数。

我在 Internet 某处找到的实现之一：

from math import *

def main():
    n = abs(input("Enter a number: "))
    i = 2
    msg = 'is a prime number.'
    while i <= sqrt(n):
        if n % i == 0:
            msg = 'is not a prime number.'
        i = i + 1
    print n, msg


main()

这里有几个问题：

  • 在上面，什么是i，为什么它的起始值为2？
  • 在这个程序中做什么i = i + 1？
  • 解释器如何知道何时打印'is a prime number.'，即使它不在正文循环中？
4

2 回答 2

4

素数是只能被 1 和自身整除的数。它使用的方法是尝试将您的候选编号除以n从 2 到自身的所有其他数字；但是，如果任何数字i是您的数字的除数，n那么也是如此，n / i并且其中至少一个小于或等于sqrt(n)因此我们只需要测试到sqrt(n)包容性。在实践中，我们只需要测试实际上是素数的除数，但由于我们手头没有素数列表，我们将测试每个素数。

上面i是什么？为什么它有一个 2 的起始值？

i是n我们正在测试的潜在因素。它以 2 开头，因为我们不在乎 1 是否除n（而且很简单），因为素数定义允许/期望。

在这个具体的例子中，i = i + 1 语句是什么？在程序中看不到它的使用。

它在由;i定义的循环结束时增加值。while i <= sqrt(n)这意味着我们提前i测试 的下一个候选除数n。

最后，python 是如何知道何时打印 'is a prime number' 的。虽然它在身体循环之外？

我们初始化msg为“是素数”，如果我们找到任何除数，那么我们在循环内将其更改为“不是素数”。如果循环没有找到除数，或者循环从未运行，我们将使用我们设置的初始值，即“是质数”。顺便说一句break，当你找到一个除数时，你可以脱离循环；在那之后进行测试是没有意义的。

另外一方面，您可能希望sqrt(n)在 while 之外计算并存储而不是在变量中使用while- 您可能会为每次迭代重新计算平方根，这相对昂贵。

于 2013-02-05T14:38:15.250 回答
2

我在两边添加了注释来解释每一行的作用：

from math import * # imports everything from the math module

def main():
    n = abs(input("Enter a number: ")) # gets input from the user
    i = 2 # starts off at 2 because all input is divisble by 1
    msg = 'is a prime number.' # the message is initially set
    while i <= sqrt(n):
        if n % i == 0: # if 'i' divides evenly into n
            msg = 'is not a prime number.' # only set if it isn't a prime
        i = i + 1 # increases 'i' by 1 so it can check every value up to the square-root of 'n' (to see if it divides evenly)
    print n, msg


main()

程序必须检查每个值i（直到 的平方根n），以便检查每个可能的因素。

这是一种粗质检查器，对于非素数的大数效率低下：如果输入是一个类似的数字1234567890，它将遍历每个数字直到该数字的平方根，即35147（向上取整） . 使用return语句会中断循环，因此您检查的第一个数字2，它被声明为非质数，因为它可以被 整除2。通过使用return，它将停止该功能，并为您节省 35,146 次计算。这不是一个庞大的数字（至少对于计算机而言），但它仍然更节省内存并且花费更少的时间。

def isPrime(n):
    '''Checks if 'n' is prime.'''
    from math import sqrt
    if n == 0 or n == 1:
        return False
    else:
        for check in range(2, int(sqrt(n))+1):
            if n % check == 0: return False
    return True
于 2013-02-05T15:09:46.627 回答