在 Internet 上流传的许多质数测试中，请考虑以下 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
由于所有大于 3 的素数都是 6n ± 1 的形式，因此一旦我们消除它n：
n%2) 和n%3），那么我们可以每 6 个 n ± 1 进行一次测试。考虑素数 5003：
print is_prime(5003)
印刷：
5
11
17
23
29
35
41
47
53
59
65
True
该行r = int(n**0.5)计算为 70（5003 的平方根为 70.7318881411 并int()截断该值）
考虑下一个奇数（因为除了 2 之外的所有偶数都不是素数）5005，同样的打印结果：
5
False
极限是平方根，因为x*y == y*x该函数只需循环 1 次即可发现 5005 可被 5 整除，因此不是素数。因为5 X 1001 == 1001 X 5（并且两者都是 5005），我们不需要在循环中一直走到 1001 来知道我们在 5 处知道的内容！
现在，让我们看看您拥有的算法：
def isPrime(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
有两个问题：
n小于 2，并且没有小于 2 的素数；所以：
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
好的——它加快了大约 30%（我对它进行了基准测试......）
我使用的算法is_prime仍然快 2 倍左右，因为只有每 6 个整数在循环中循环。（再一次，我对它进行了基准测试。）
旁注：x**0.5 是平方根：
>>> import math
>>> math.sqrt(100)==100**0.5
True
旁注 2：素数测试是计算机科学中一个有趣的问题。
使用n**.5，您不是对 n 求平方，而是取平方根。
考虑数字 20；整数因子是 1、2、4、5、10 和 20。当你将 20 除以 2 得到 10 时，你知道它也能被 10 整除，无需检查。当你将它除以 4 并得到 5 时，你知道它可以被 4 和 5 整除，而无需检查 5。
达到因子的中间点后，您将没有更多的数字可以检查您之前尚未识别为因子的数字。因此，你只需要走到一半就可以看是否是素数，而这个中点可以通过取数的平方根来找到。
此外，1 不是素数的原因是因为素数被定义为具有 2 个因数，即 1 和它本身。即 2 是 1*2，3 是 1*3，5 是 1*5。但是 1 (1*1) 本身只有 1 个因子。因此，它不符合这个定义。
这个问题是不久前提出的，但我有一个更短的解决方案给你
def isNotPrime(Number):
return 2 not in [Number,2**Number%Number]
如果数字是素数，数学运算将主要返回 2，而不是 2。但如果 2 是给定的数字，它会附加到我们正在查看的列表中。
例子：
2^5=32 32%5=2
2^7=128 128%7=2
2^11=2048 2048%11=2
反例：
2^341%341=2, but 341==11*31
2^561%561=2, but 561==3*11*17
2^645%645=2, but 645==3*5*43
如果 Number 不是素数，isNotPrime() 可靠地返回 True。
下面没有进行浮点运算。这更快，并且可以容忍更高的参数。你必须只求平方根的原因是，如果一个数有一个大于它的平方根的因数，它也有一个比它小的因数。
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
这种方法会比这里的递归和枚举方法慢，但使用威尔逊定理，并且只有一行：
from math import factorial
def is_prime(x):
return factorial(x - 1) % x == x - 1
找到数字的平方根是为了提高效率。例如。如果我试图找到 36 的因数，可以乘以自身形成 36 的最大数是 6. 7*7 = 49。
因此，每个 36 的因数都必须乘以 6 或更小的数字。
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
def isPrime(num,div=2):
if(num==div):
return True
elif(num % div == 0):
return False
else:
return isPrime(num,div+1)
===============================================
已编辑
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)
我不知道我是否迟到了，但我会把它留在这里以帮助将来的人。
我们使用 (n) 的平方根，即 int(n**0.5) 来减少您的程序将被迫计算的数字范围。
例如，我们可以做一个试验除法来测试 100 的素数。让我们看看 100 的所有除数：
2, 4, 5, 10, 20, 25, 50 这里我们看到最大的因子是 100/2 = 50。这对所有 n 都是正确的：所有除数都小于或等于 n/2。如果我们仔细看看除数，我们会发现其中一些是多余的。如果我们以不同的方式编写列表：
100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 冗余变得明显。一旦我们达到 10，即 √100，除数就会翻转并重复。因此，我们可以进一步消除大于 √n 的测试除数。
取另一个数字，例如 16。
它的除数是 2,4,8
16 = 2 * 8、4 * 4、8 * 2。
您可以注意到，在达到 4（即 16 的平方根）之后，我们重复了 8 * 2，我们已经将其作为 2*8。这种模式适用于所有数字。
为了避免重复自己，我们因此测试素数直到数字 n 的平方根。
所以我们将平方根转换为 int，因为我们不想要一个带有浮点数的范围。
阅读维基百科上的素数测试以获取更多信息。
这是我的方法：
import math
def isPrime(n):
'Returns True if n is prime, False if n is not prime. Will not work if n is 0 or 1'
# Make sure n is a positive integer
n = abs(int(n))
# Case 1: the number is 2 (prime)
if n == 2: return True
# Case 2: the number is even (not prime)
if n % 2 == 0: return False
# Case 3: the number is odd (could be prime or not)
# Check odd numbers less than the square root for possible factors
r = math.sqrt(n)
x = 3
while x <= r:
if n % x == 0: return False # A factor was found, so number is not prime
x += 2 # Increment to the next odd number
# No factors found, so number is prime
return True
要回答原始问题，n**0.5与 n 的平方根相同。您可以在此数字之后停止检查因数，因为合数的因数总是小于或等于其平方根。这比只检查每个 n 的 2 和 n 之间的所有因子要快，因为我们检查的数字更少，随着 n 的增长，这可以节省更多的时间。
isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:])
这里是如何使用它
isPrime(2) == False
isPrime(5) == True
isPrime(7) == True
要查找您可能使用的所有素数：
filter(isPrime, range(4000)[2:])[:5]
=> [2, 3, 5, 7, 11]
请注意，在这种情况下，5 表示要找到的素数的数量和 4000 最大范围的素数将被查找。
def is_prime(x):
if x < 2:
return False
for n in range(2, (x) - 1):
if x % n == 0:
return False
return True
您编写的每个代码都应该是高效的。对于像您这样的初学者，最简单的方法是检查数字'n'从2 到 (n-1)的整除性。当您考虑非常大的数字时，这需要很多时间。平方根方法通过较少的比较次数帮助我们使代码更快。阅读算法设计和分析的复杂性。
在 python 中实现了一个伪代码（https://en.wikipedia.org/wiki/Primality_test ），希望对您有所帮助。
# original pseudocode https://en.wikipedia.org/wiki/Primality_test
def isPrime(n):
# Corner Cases
if (n<= 1): return False
elif (n<= 3): return True
elif (n%2 == 0 or n%3 == 0): return False
i = 5
while i*i<=n:
if (n%i==0 or n%(i+2)==0): return False
i += 6
return True;
%timeit isPrime(800)
int(n**0.5)是您与 n 的幂 2 混淆的 sqrt(n) 的底值(n**2)。如果n不是素数，则必须有两个数1 < i <= j < n：i * j = n。
现在，由于sqrt(n) * sqrt(n) = n假设其中一个i,j大于（或等于）sqrt(n)- 这意味着另一个必须小于（或等于）sqrt(n)。
既然是这样，迭代 range 中的整数就足够了 [2, sqrt(n)]。这正是发布的代码正在做的事情。
如果您想成为真正的聪明人，请使用以下单行函数：
import re
def is_prime(n):
return not re.match(r'^1?$|^(11+?)\1+$',n*'1')
这是我的np方式：
def is_prime(x):
if x < 4:
return True
if all([(x > 2), (x % 2 == 0)]):
return False
else:
return np.array([*map(lambda y: ((x % y) == 0).sum(), np.arange(1, x + 1))]).sum() == 2
这是表演：
%timeit is_prime(2)
%timeit is_prime(int(1e3))
%timeit is_prime(5003)
10000 loops, best of 3: 31.1 µs per loop
10000 loops, best of 3: 33 µs per loop
10 loops, best of 3: 74.2 ms per loop
def is_prime(n):
n=abs(n)
if n<2: #Numbers less than 2 are not prime numbers
return "False"
elif n==2: #2 is a prime number
return "True"
else:
for i in range(2,n): # Highlights range numbers that can't be a factor of prime number n.
if n%i==0:
return "False" #if any of these numbers are factors of n, n is not a prime number
return "True" # This is to affirm that n is indeed a prime number after passing all three tests
这是codecademy中的一个练习，这就是我在下面通过它的方式......
def is_prime(x):
# If number(x) is evenly divided by following dividers then number(x) is not prime
divider = [2, 3, 5, 7]
# An empty list to be able to check whether number(x) is evenly divided:
remainder = []
# exceptions for numbers 1,2,3,5,7:
if x < 2:
return False
if x in divider:
return True
else:
for nums in divider:
remainder.append(x % nums)
if 0 in remainder:
return False
else:
return True
def is_prime(n):
if (n==2 or n==3): return True
if(n<=1 or n%2==0 or n%3==0 ): return False
for i in range(6,int((n**0.5)) + 2,6):
if(n%(i-1)==0 or n%(i+1)==0):
return False
return True
这是该网站的答案。
def is_Prime(n):
if n <= 3:
return n > 1
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i ** 2 <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
isPrime=list()
c=-1
for i in range(0,1000001):
c=c+1
isPrime.append(c)
if is_Prime(isPrime[i])==True:
isPrime[i]=True
else:
isPrime[i]=False
这整个解决方案是基于因素的。恰好有两个因数（即 1 和数字本身）的自然数是质数。简单来说，如果一个数只能被 1 和它自己整除，那么它就是质数。除数字 2 外，所有质数都是奇数。
def isprime(x):
factors=[]
if x < 2:
return False
for i in range(1,x+1):
if (x % i == 0):
factors.append(i)
return True if len(factors) <=2 else False
很简单！
def prime(x):
if x == 1:
return False
else:
for a in range(2,x):
if x % a == 0:
return False
return True
这是我的
import math
def is_prime(num):
if num % 2 == 0 and num > 2:
return False
for i in range(3, int(math.sqrt(num)) + 1, 2):
if num % i == 0:
return False
return True
def fun(N):#prime test
if N>1 :
for _ in xrange(5):
Num=randint(1,N-1)
if pow(Num,N-1,N)!=1:
return False
return True
return False
如果数字是素数则为真，否则为假
数字 1 是一种特殊情况，它既不是素数也不是合数。欲了解更多信息，请访问： http: //mathworld.wolfram.com/PrimeNumber.html
而且，(n**0.5) --> 这将给我们“n”的“平方根”。因为它是“n 次幂 0.5 或 1/2”
我们为什么要这样做，以数字 400 为例：我们可以用 a*b 的形式表示它
1*400 = 400
2*200 = 400
4*100 = 400
5*80 = 400
8*50 = 400
10*40 = 400
16*25 = 400
20*20 = 400
25*16 = 400
40*10 = 400
50*8 = 400
80*5 = 400
100*4 = 400
200*2 = 400
400*1 = 400
400 的平方根是 20：我们可以看到，我们只需要检查直到 20 的可分性，因为当 'a' 达到 20 时，'b' 开始减少......所以，最终我们用小于的数字检查可分性平方根。
我有一个新的解决方案，我认为它可能比 Python 中提到的任何函数都快
它基于这样的想法：对于任意数 N，N/D = R，除以 N（如果不是素数）的最小可能数是 D=2，相应的结果 R 是 (N/2)（最高）。
随着 D 变大，结果 R 变小 例如：除以 D = 3 结果 R = (N/3) 所以当我们检查 N 是否可被 D 整除时，我们也在检查它是否可被 R 整除
所以随着 D 变大而 R 变小直到 (D == R == 平方根(N))
那么我们只需要检查从 2 到 sqrt(N) 的数字另一个提示以节省时间，我们只需要检查奇数，因为它可以被任何偶数整除，它也可以被 2 整除。
所以序列将是 3,5,7,9,......,sqrt(N)。
import math
def IsPrime (n):
if (n <= 1 or n % 2 == 0):return False
if n == 2:return True
for i in range(3,int(math.sqrt(n))+1,2):
if (n % i) == 0:
return False
return True
( https://www.youtube.com/watch?v=Vxw1b8f_yts&t=3384s ) Avinash Jain
for i in range(2,5003):
j = 2
c = 0
while j < i:
if i % j == 0:
c = 1
j = j + 1
else:
j = j + 1
if c == 0:
print(str(i) + ' is a prime number')
else:
c = 0
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
Srsly 伙计们......为什么像这样的简单方法需要这么多行代码？这是我的解决方案：
def isPrime(a):
div = a - 1
res = True
while(div > 1):
if a % div == 0:
res = False
div = div - 1
return res