在 Python 中检查一个数字是否是质数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4114167/
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
Checking if a number is a prime number in Python
提问by steve
I have written the following code, which should check if the entered number is a prime number or not, but there is an issue i couldn't get through:
我写了下面的代码，它应该检查输入的数字是否是质数，但有一个我无法解决的问题：
def main():
n = input("Please enter a number:")
is_prime(n)
def is_prime(a):
x = True
for i in (2, a):
while x:
if a%i == 0:
x = False
else:
x = True
if x:
print "prime"
else:
print "not prime"
main()
If the entered number is not a prime number, it displays "not prime", as it is supposed to, but if the number is a prime number, it doesn't display anything. Could you please help me with it?
如果输入的数字不是质数，它会显示“非质数”，正如它应该的那样，但如果数字是质数，它不会显示任何内容。你能帮我吗？
回答by Jochen Ritzel
If ais a prime then the while x:in your code will run forever, since xwill remain True.
如果a是素数，那么while x:您的代码中的 将永远运行，因为x将保持True.
So why is that whilethere?
那为什么会这样while呢？
I think you wanted to end the for loop when you found a factor, but didn't know how, so you added that while since it has a condition. So here is how you do it:
我认为您想在找到一个因素时结束 for 循环，但不知道如何结束，所以您添加了 while，因为它有一个条件。所以这是你如何做到的：
def is_prime(a):
x = True
for i in range(2, a):
if a%i == 0:
x = False
break # ends the for loop
# no else block because it does nothing ...
if x:
print "prime"
else:
print "not prime"
回答by Jochen Ritzel
There are many efficient ways to test primality (and this isn't one of them), but the loop you wrote can be concisely rewritten in Python:
有许多有效的方法来测试素性（这不是其中之一），但是您编写的循环可以用 Python 简洁地重写：
def is_prime(a):
return all(a % i for i in xrange(2, a))
That is, a is prime if all numbers between 2 and a (not inclusive) give non-zero remainder when divided into a.
也就是说，如果 2 和 a 之间的所有数字（不包括 2 和 a）在除以 a 时给出非零余数，则 a 是素数。
回答by Dhooom
a = input('inter a number: ')
s = 0
if a == 1:
print a, 'is a prime'
else :
for i in range (2, a ):
if a%i == 0:
print a,' is not a prime number'
s = 'true'
break
if s == 0 : print a,' is a prime number'
it worked with me just fine :D
它和我一起工作得很好：D
回答by Mark
This is the most efficient way to see if a number is prime, if you only have a few query. If you ask a lot of numbers if they are prime try Sieve of Eratosthenes.
如果您只有几个查询，这是查看数字是否为素数的最有效方法。如果您问很多数字是否为素数，请尝试使用埃拉托色尼筛法。
import math
def is_prime(n):
if n == 2:
return True
if n % 2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n % divisor == 0:
return False
return True
回答by Mesut014
def isPrime(x):
if x<2:
return False
for i in range(2,x):
if not x%i:
return False
return True
print isPrime(2)
True
print isPrime(3)
True
print isPrime(9)
False
打印 isPrime(2)
真
打印 isPrime(3)
真
打印 isPrime(9)
假
回答by Fadyboy
def prime(x):
# check that number is greater that 1
if x > 1:
for i in range(2, x + 1):
# check that only x and 1 can evenly divide x
if x % i == 0 and i != x and i != 1:
return False
else:
return True
else:
return False # if number is negative
回答by Shree Ranga Raju
def is_prime(x):
n = 2
if x < n:
return False
else:
while n < x:
print n
if x % n == 0:
return False
break
n = n + 1
else:
return True
回答by Marco Bonelli
Here is my take on the problem:
这是我对这个问题的看法：
from math import sqrt; from itertools import count, islice
def is_prime(n):
return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
This is a really simple and concise algorithm, and therefore it is not meant to be anything near the fastest or the most optimal primality check algorithm. It has a time complexity of O(sqrt(n)). Head over hereto learn more about primality tests done right and their history.
这是一个非常简单和简洁的算法，因此它并不意味着接近最快或最优化的素性检查算法。它的时间复杂度为O(sqrt(n))。头以上，这里了解更多关于做对素性测试和他们的历史。
Explanation
解释
I'm gonna give you some insides about that almost esoteric single line of code that will check for prime numbers:
我会给你一些关于将检查素数的几乎深奥的单行代码的一些内幕：
First of all, using
range()is really a bad idea, because it will create a list of numbers, which uses a lot of memory. Usingxrange()is better, because it creates a generator, which only needs to memorize the initial arguments you provide, and generates every number on-the-fly. If you're using Python 3 or higherrange()has been converted to a generator by default. By the way, this is not the best solution at all: trying to callxrange(n)for somensuch thatn > 231-1(which is the maximum value for a Clong) raisesOverflowError. Therefore the best way to create a range generator is to useitertools:xrange(2147483647+1) # OverflowError from itertools import count, islice count(1) # Count from 1 to infinity with step=+1 islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1 islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3You do not actually need to go all the way up to
nif you want to check ifnis a prime number. You can dramatically reduce the tests and only check from 2 to√(n)(square root ofn). Here's an example:Let's find all the divisors of
n = 100, and list them in a table:2 x 50 = 100 4 x 25 = 100 5 x 20 = 100 10 x 10 = 100 <-- sqrt(100) 20 x 5 = 100 25 x 4 = 100 50 x 2 = 100You will easily notice that, after the square root of
n, all the divisors we find were actually already found. For example20was already found doing100/5. The square root of a number is the exact mid-point where the divisors we found begin being duplicated. Therefore, to check if a number is prime, you'll only need to check from 2 tosqrt(n).Why
sqrt(n)-1then, and not justsqrt(n)? That's because the second argument provided toitertools.isliceobject is the number of iterations to execute.islice(count(a), b)stops afterbiterations. That's the reason why:for number in islice(count(10), 2): print number, # Will print: 10 11 for number in islice(count(1, 3), 10): print number, # Will print: 1 4 7 10 13 16 19 22 25 28The function
all(...)is the same of the following:def all(iterable): for element in iterable: if not element: return False return TrueIt literally checks for all the numbers in the
iterable, returningFalsewhen a number evaluates toFalse(which means only if the number is zero). Why do we use it then? First of all, we don't need to use an additional index variable (like we would do using a loop), other than that: just for concision, there's no real need of it, but it looks way less bulky to work with only a single line of code instead of several nested lines.
首先，使用
range()确实是一个坏主意，因为它会创建一个数字列表，这会占用大量内存。使用xrange()更好，因为它创建了一个generator，它只需要记住你提供的初始参数，并即时生成每个数字。如果您使用的是 Python 3 或更高版本range()，则默认情况下已转换为生成器。顺便说一句，这根本不是最好的解决方案：试图调用xrange(n)一些n这样的（这是 C 的最大值） raise 。因此，创建范围生成器的最佳方法是使用：n > 231-1longOverflowErroritertoolsxrange(2147483647+1) # OverflowError from itertools import count, islice count(1) # Count from 1 to infinity with step=+1 islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1 islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3n如果您想检查是否n是素数，您实际上并不需要一路向上。您可以显着减少测试，只检查 2 到√(n)（的平方根n）。下面是一个例子：让我们找出 的所有除数
n = 100，并在表中列出它们：2 x 50 = 100 4 x 25 = 100 5 x 20 = 100 10 x 10 = 100 <-- sqrt(100) 20 x 5 = 100 25 x 4 = 100 50 x 2 = 100你会很容易注意到，在 的平方根之后
n，我们找到的所有除数实际上都已经找到了。例如20已经发现在做100/5。数字的平方根是我们发现的除数开始复制的确切中点。因此，要检查一个数是否为质数，您只需检查从 2 到sqrt(n).sqrt(n)-1那么为什么，而不仅仅是sqrt(n)？那是因为提供给itertools.isliceobject的第二个参数是要执行的迭代次数。迭代islice(count(a), b)后停止b。这就是为什么：for number in islice(count(10), 2): print number, # Will print: 10 11 for number in islice(count(1, 3), 10): print number, # Will print: 1 4 7 10 13 16 19 22 25 28功能
all(...)与以下相同：def all(iterable): for element in iterable: if not element: return False return True它从字面上检查 中的所有数字
iterable，False当数字计算为时返回False（这意味着仅当数字为零时）。那我们为什么要使用它呢？首先，我们不需要使用额外的索引变量（就像我们使用循环所做的那样），除此之外：只是为了简洁，没有真正需要它，但它看起来不那么笨重，只使用一行代码而不是几行嵌套的代码。
Extended version
扩大的视野
I'm including an "unpacked" version of the isPrime()function, to make it easier to understand and read it:
我包含了该isPrime()函数的“解压缩”版本，以使其更易于理解和阅读：
from math import sqrt
from itertools import count, islice
def is_prime(n):
if n < 2:
return False
for number in islice(count(2), int(sqrt(n) - 1)):
if n % number == 0:
return False
return True
