Python 语言的 isPrime 函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15285534/
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
isPrime Function for Python Language
提问by Giancarlo Manuel Guerra Salvá
So I was able to solve this problem with a little bit of help from the internet and this is what I got:
所以我能够在互联网的帮助下解决这个问题，这就是我得到的：
def isPrime(n):
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
return True
But my question really is how to do it, but WHY. I understand that 1 is not considered a "prime" number even though it is, and I understand that if it divides by ANYTHING within the range it is automatically prime thus the return False statement. but my question is what role does the squaring the "n" play here? Thank you very much for your attention
但我的问题确实是如何做到这一点，但为什么。我明白 1 不被视为“质数”，即使它是，我明白如果它除以范围内的任何东西，它会自动成为质数，因此返回 False 语句。但我的问题是“n”的平方在这里扮演什么角色？非常感谢您的关注
P.s. I am very inexperienced and have just been introduced to programming a month ago :S
Ps 我非常缺乏经验，一个月前才开始接触编程：S
采纳答案by dawg
Of many prime number tests floating around the Internet, consider the following Python function:
在互联网上流传的许多质数测试中，请考虑以下 Python 函数：
def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**0.5)
# since all primes > 3 are of the form 6n ± 1
# start with f=5 (which is prime)
# and test f, f+2 for being prime
# then loop by 6.
f = 5
while f <= r:
print('\t',f)
if n % f == 0: return False
if n % (f+2) == 0: return False
f += 6
return True
Since all primes > 3are of the form 6n ± 1, once we eliminate that nis:
由于所有 > 3 的质数都具有 6n ± 1 的形式，因此一旦我们消除它n：
- not 2 or 3 (which are prime) and
- not even (with
n%2) and - not divisible by 3 (with
n%3) then we can test every 6th n ± 1.
- 不是 2 或 3（质数）和
- 甚至（与
n%2）和 - 不能被 3 (with
n%3)整除，那么我们可以每第 6 个 n ± 1 进行测试。
Consider the prime number 5003:
考虑素数 5003：
print is_prime(5003)
Prints:
印刷：
5
11
17
23
29
35
41
47
53
59
65
True
The line r = int(n**0.5)evaluates to 70 (the square root of 5003 is 70.7318881411 and int()truncates this value)
该行r = int(n**0.5)计算结果为 70（5003 的平方根为 70.7318881411 并int()截断此值）
Consider the next odd number (since all even numbers other than 2 are not prime) of 5005, same thing prints:
考虑 5005 的下一个奇数（因为除 2 之外的所有偶数都不是质数），同样的事情打印：
5
False
The limit is the square root since x*y == y*xThe function only has to go 1 loop to find that 5005 is divisible by 5 and therefore not prime. Since 5 X 1001 == 1001 X 5(and both are 5005), we do not need to go all the way to 1001 in the loop to know what we know at 5!
极限是平方根，因为x*y == y*x该函数只需执行 1 个循环即可发现 5005 可被 5 整除，因此不是素数。因为5 X 1001 == 1001 X 5（并且都是 5005），我们不需要一直走到循环中的 1001 来知道我们在 5 处知道什么！
Now, let's look at the algorithm you have:
现在，让我们看看您拥有的算法：
def isPrime(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
There are two issues:
有两个问题：
- It does not test if
nis less than 2, and there are no primes less than 2; - It tests every number between 2 and n**0.5 including all even and all odd numbers. Since every number greater than 2 that is divisible by 2 is not prime, we can speed it up a little by only testing odd numbers greater than 2.
- 不测试是否
n小于2，也没有小于2的素数； - 它测试 2 和 n**0.5 之间的每个数字，包括所有偶数和所有奇数。由于每个可以被 2 整除的大于 2 的数都不是质数，我们可以通过只测试大于 2 的奇数来加快速度。
So:
所以：
def isPrime2(n):
if n==2 or n==3: return True
if n%2==0 or n<2: return False
for i in range(3, int(n**0.5)+1, 2): # only odd numbers
if n%i==0:
return False
return True
OK -- that speeds it up by about 30% (I benchmarked it...)
好的——这将它的速度提高了大约 30%（我对它进行了基准测试......）
The algorithm I used is_primeis about 2x times faster still, since only every 6th integer is looping through the loop. (Once again, I benchmarked it.)
我使用的算法is_prime仍然快 2 倍，因为只有每 6 个整数在循环中循环。（我再一次对其进行了基准测试。）
Side note: x**0.5 is the square root:
旁注：x**0.5 是平方根：
>>> import math
>>> math.sqrt(100)==100**0.5
True
Side note 2: primality testingis an interesting problem in computer science.
旁注 2：素性测试是计算机科学中的一个有趣问题。
回答by ncmathsadist
No floating point operations are done below. This is faster and will tolerate higher arguments. The reason you must go only to the square-root is that if a number has a factor larger than its square root, it also has a factor smaller than it.
下面没有进行浮点运算。这更快，并且可以容忍更高的参数。你必须只求平方根的原因是，如果一个数的因数大于它的平方根，那么它也有一个比它小的因数。
def is_prime(n):
""""pre-condition: n is a nonnegative integer
post-condition: return True if n is prime and False otherwise."""
if n < 2:
return False;
if n % 2 == 0:
return n == 2 # return False
k = 3
while k*k <= n:
if n % k == 0:
return False
k += 2
return True
回答by cpuguy89
With n**.5, you are not squaring n, but taking the square root.
使用n**.5，您不是在平方 n，而是求平方根。
Consider the number 20; the integer factors are 1, 2, 4, 5, 10, and 20. When you divide 20 by 2 and get 10, you know that it is also divisible by 10, without having to check. When you divide it by 4 and get 5, you know it is divisible by both 4 and 5, without having to check for 5.
考虑数字 20；整数因子有1、2、4、5、10和20。当你将20除以2得到10时，你知道它也能被10整除，不用检查。当你将它除以 4 得到 5 时，你知道它可以被 4 和 5 整除，而不必检查 5。
After reaching this halfway point in the factors, you will have no more numbers to check which you haven't already recognized as factors earlier. Therefore, you only need to go halfway to see if something is prime, and this halfway point can be found by taking the number's square root.
达到因子的中点后，您将没有更多的数字可供检查，而您之前尚未将其识别为因子。因此，你只需要中途看看某个东西是否是质数，这个中点可以通过取数字的平方根来找到。
Also, the reason 1 isn't a prime number is because prime numbers are defined as having 2 factors, 1 and itself. i.e 2 is 1*2, 3 is 1*3, 5 is 1*5. But 1 (1*1) only has 1 factor, itself. Therefore, it doesn't meet this definition.
此外，1 不是质数的原因是因为质数被定义为具有 2 个因数，1 和它本身。即 2 是 1*2，3 是 1*3，5 是 1*5。但是 1 (1*1) 本身只有 1 个因子。因此，它不符合这个定义。
回答by dibble
Finding the square root of the number is for efficiency. eg. if I am trying to find the factors of 36, the highest number that can be multiplied by itself to form 36 is 6. 7*7 = 49.
求数字的平方根是为了提高效率。例如。如果我试图找到 36 的因数，则可以自乘以形成 36 的最大数是 6。7*7 = 49。
therefore every factor of 36 has to be multiplied by 6 or a lesser number.
因此，36 的每个因数都必须乘以 6 或更小的数。
回答by namco
def isPrime(num,div=2):
if(num==div):
return True
elif(num % div == 0):
return False
else:
return isPrime(num,div+1)
==============================================
EDITED
==============================================
编辑
def is_prime(num, div = 2):
if num == div: return True
elif num % div == 0: return False
elif num == 1: return False
else: return is_prime(num, div + 1)
回答by user3897549
def is_prime(x):
if x<2:
return False
elif x == 2:
return True
else:
for n in range(2, x):
if x%n==0:
return False
return True
回答by likarson
def is_prime(x):
if x < 2:
return False
elif x == 2:
return True
for n in range(2, x):
if x % n ==0:
return False
return True
回答by AGSoldier
Srsly guys... Why so many lines of code for a simple method like this? Here's my solution:
Srsly 伙计们...为什么像这样的简单方法需要这么多行代码？这是我的解决方案：
def isPrime(a):
div = a - 1
res = True
while(div > 1):
if a % div == 0:
res = False
div = div - 1
return res
回答by test30
isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:])
and here goes how to use it
这是如何使用它
isPrime(2) == False
isPrime(5) == True
isPrime(7) == True
To find all primes you might use:
要查找您可能使用的所有素数：
filter(isPrime, range(4000)[2:])[:5]
=> [2, 3, 5, 7, 11]
Note that 5, in this case, denotes number of prime numbers to be found and 4000 max range of where primes will be looked for.
请注意，在这种情况下，5 表示要找到的素数的数量和 4000 将寻找素数的最大范围。
回答by alfasin
int(n**0.5)is the floor value of sqrt(n) which you confused with power 2 of n (n**2). If nis notprime, there must be two numbers 1 < i <= j < nsuch that: i * j = n.
int(n**0.5)是 sqrt(n) 的下限值，您将其与 n 的 2 次方混淆(n**2)。如果n是没有黄金，必须有两个号码1 < i <= j < n这样的：i * j = n。
Now, since sqrt(n) * sqrt(n) = nassuming one of i,jis bigger than (or equals to) sqrt(n)- it means that the other one has to be smaller than (or equals to) sqrt(n).
现在，由于sqrt(n) * sqrt(n) = n假设其中之一i,j大于（或等于）sqrt(n)- 这意味着另一个必须小于（或等于）sqrt(n)。
Since that is the case, it's good enough to iterate the integer numbers in the range [2, sqrt(n)]. And that's exactly what the code that was posted is doing.
既然是这样，那么迭代范围内的整数就足够了 [2, sqrt(n)]。这正是发布的代码所做的。
If you want to come out as a real smartass, use the following one-liner function:
如果你想成为一个真正的聪明人，请使用以下单行函数：
import re
def is_prime(n):
return not re.match(r'^1?$|^(11+?)+$',n*'1')
An explanation for the "magic regex" can be found here
可以在此处找到“魔术正则表达式”的解释
