Python 语言的 isPrime 函数

问题描述：

因此，我借助互联网的帮助解决了这个问题，结果如下：

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
        
    return True

但我的问题实际上是如何做到这一点，但为什么。我知道 1 不被视为“质数”，尽管它是，我也知道如果它除以范围内的任何数，它就自动不是质数，因此返回 False 语句。但我的问题是“n”的平方根在这里起什么作用？

附言：我非常缺乏经验，一个月前才开始接触编程。

解决方案 1：

在互联网上流传的许多素数测试中，请考虑以下 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('    ',f)
    if n % f == 0: return False
    if n % (f+2) == 0: return False
    f += 6
  return True    

由于所有 > 3 的素数都是 6n ± 1 的形式，一旦我们消去它，n就有：

1. 不是 2 或 3（它们是质数），并且

2. 甚至没有（与n%2）和

3. 不能被 3 整除（并且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

有两个问题：

1. 它不测试是否n小于 2，并且没有小于 2 的素数；

2. 它测试 2 到 n**0.5 之间的所有数字，包括所有偶数和奇数。由于每个大于 2 且能被 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：素数测试是计算机科学中一个有趣的问题。

解决方案 2：

使用n**.5，您不是在求 n 的平方，而是在求平方根。

考虑数字 20；整数因数为 1、2、4、5、10 和 20。当您用 20 除以 2 并得到 10 时，您知道它也可以被 10 整除，而不必检查。当您用 4 除以 5 并得到 5 时，您知道它既可以被 4 整除，又可以被 5 整除，而不必检查 5。

在达到因数的这个中间点后，您将没有更多数字需要检查，因为您之前还没有将数字识别为因数。因此，您只需走到一半即可查看某个数字是否为素数，而这个中间点可以通过取数字的平方根来找到。

另外，1 不是质数的原因在于质数被定义为具有 2 个因数，即 1 和它本身。例如 2 是 12，3 是 13，5 是 15。但是 1（11）只有一个因数，即它本身。因此，它不符合这个定义。

解决方案 3：

这个问题是不久前提出的，但我有一个更简短的解决方案给你

def isNotPrime(number):
    return 2 not in [number, pow(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 。

解决方案 4：

下面不进行浮点运算。这样速度更快，并且可以容忍更高的参数。必须只求平方根的原因是，如果一个数有一个大于其平方根的因数，那么它也有一个小于它的因数。

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

解决方案 5：

这种方法会比这里的递归和枚举方法慢，但使用了威尔逊定理，并且只有一行：

from math import factorial

def is_prime(x):
    return factorial(x - 1)  % x == x - 1

解决方案 6：

求数字的平方根是为了提高效率。例如，如果我试图找出 36 的因数，那么能与自身相乘得到 36 的最大数字是 6。7*7 = 49。

因此，36 的每个因数都必须乘以 6 或更小的数字。

解决方案 7：

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

解决方案 8：

这是我的方法：

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 

回答原始问题，n0.5*等于n 的根的平方。您可以停止检查此数字之后的因数，因为合数的因数始终*小于或等于其平方根。这比只检查 2 和 n 之间的所有因数要快，因为我们检查的数字更少，随着 n 的增长，这会节省更多时间。

解决方案 9：

def is_prime(x):  
    if x < 2:  
        return False  
    for n in range(2, (x) - 1):  
        if x % n == 0:  
            return False  
    return True

解决方案 10：

我不知道我是否迟了，但我会把它留在这里以便将来帮助别人。

我们使用（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，而之前我们已经将其作为 28 进行过计算。此模式适用于所有数字。

为了避免重复，我们测试数字 n 的平方根的素数。

因此，我们将平方根转换为 int，因为我们不想要浮点数的范围。

阅读维基百科上的素数测试以获取更多信息。

解决方案 11：

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)

解决方案 12：

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。

解决方案 13：

您编写的每个代码都应该是高效的。对于像您这样的初学者来说，最简单的方法是检查数字“n”从2 到 (n-1)的可整除性。当您考虑非常大的数字时，这会花费大量时间。平方根方法通过减少比较次数帮助我们加快代码速度。阅读算法设计和分析中的复杂性。

解决方案 14：

int(n**0.5)是 sqrt(n) 的底值，您将其与 n 的 2 次方混淆了。(n**2)如果n不是素数，则必须有两个数字使得：。1 < i <= j < n`i * j = n`

现在，由于sqrt(n) * sqrt(n) = n假设其中一个i,j大于（或等于）sqrt(n)- 这意味着另一个必须小于（或等于）sqrt(n)。

既然如此，迭代范围内的整数就足够了 [2, sqrt(n)]。这正是发布的代码所做的事情。

如果您想成为一个真正的聪明人，请使用以下单行函数：

import re
def is_prime(n):    
    return not re.match(r'^1?$|^(11+?)
+$',n*'1')

关于“魔法正则表达式”的解释可以在这里找到

解决方案 15：

用 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)

解决方案 16：

我们知道，从 2 开始的自然数：{2、3、4、5、6、7、...}如果只能被 1 和自身整除，则被视为质数。第一个也是唯一一个偶质数是 2。接下来的质数是：3、5、7、11、13、17、19、23、29、...，以及无穷多个质数。

从编程角度来看，有许多涉及素数的算法。最简单和最无效的方法（幼稚版本）是根据定义进行测试，即测试N是否能被除数 2 [2..N-1] 整除。这种方法可行，但就除法次数而言，其运行时间为 O(N)。这不是最好的方法，还有几种可能的改进方法。

第一个改进是测试 N 是否能被除数 2 [2..sqrt(N)] 整除，即当除数大于sqrt(N)时停止。我们声称，如果 a b = N，则 a <= sqrt(N) 或 b <= sqrt(N)。通过反证法快速证明：假设情况并非如此，即 a > sqrt(N) 和 b > sqrt(N)。这意味着 a b > sqrt(N) sqrt(N) 或 a b > N。此改进为 O(sqrt(N))，这已经比之前的简单版本快得多，但仍然可以改进为两倍。

第二个改进是测试 N 是否能被除数 2 [3, 5, ..., sqrt(N)] 整除，即我们只测试最大为 sqrt(N) 的奇数。这是因为只有一个偶素数，即数字 2，可以单独测试。这是它的代码，但您甚至可以优化此代码以获得更好的性能。

def is_prime(number):
    if number <= 1:
        return False
    elif number == 2:
        return True
    elif number % 2 == 0:
        return False
    else:
        # Check for divisibility from 3 up to the square root of the number
        for i in range(3, int(number**0.5) + 1, 2):
            if number % i == 0:
                return False
        return True

使用示例：

num = int(input("Enter a number: "))
if is_prime(num):
    print(f"{num} is a prime number.")
else:
    print(f"{num} is not a prime number.")

解决方案 17：

记住操作顺序很重要。这样做可以消除无用的分支，从而降低性能，并且只在必要时检查特殊罕见情况。没有必要检查除非n == 2是n奇数。并且没有必要检查除非n <= 1除了n自身和 1 之外是否不能被任何正数整除，因为这是一种罕见的特殊情况。此外，检查if not n%5速度较慢，至少在 Python 中是这样。这就是我在 3 中停止的原因。

from math import sqrt
def is_prime(n):
    if not n%2: return n==2
    if not n%3: return n==3
    for i in range(5,int(sqrt(n))+1,2):
        if not n%i: return False
    return n>1

这是一个更快的解决方案，它不检查 2 和 3 的乘数（在循环中），而只检查 2。顺便说一句，我存储了它int(sqrt(n))以防止 while 循环在每次迭代中计算它。

def is_prime(n):
    if not n&1: return n==2
    if not n%3: return n==3
    i,r=5,int(sqrt(n))
    while i<=r:
        if not n%i or not n%(i+2): return False
        i+=6
    return n>1

解决方案 18：

回答标题中的问题：使用from sympy import isprime。

回答关于“平方根”的问题：要检查n是否为素数，只需寻找不超过 √ n 的因数，因为对于任何较大的因数q，都会有较小的因数n/q。

关于给定的算法，用从 2 到 √ n 的所有数字进行试除是极其低效的，因为几乎所有数字 () 都不是素数，而且尝试这些数字是没有用的，因为如果n是i = p q的倍数，那么它也将是较小因子p的倍数，而这个因子早就被发现了。因此，至少应该只检查奇数i，这非常简单：只需使用步长— 当然，首先检查n确实是奇数（带有）。如果您没有/不想创建足够大的“预先计算”素数列表，则仅检查素数除数的“更好”选项会更复杂，甚至可能效率不高。）for k in range(3, isqrt(n)+1, 2): ...`2`if not n&1: return n==2

isqrt()（我使用了最近添加到库中的“整数平方根”函数math，而不是int(n**0.5)，尽管这对于所有实际用途来说都应该没问题：它有点“丑陋”并且可能在其他情况下为较大的n导致问题，但我们的循环永远无法达到足够大的数字以至于出现问题：标准浮点数有 53 位或 16 位十进制精度，因此在达到该值超过 10^16 的数字之前不会出现问题，并且在循环中达到这样的值需要“永远”。）

（*）“几乎所有”都有精确的数学含义（谷歌一下），但在这里，将其读作“绝大多数”就足够了——特别是所有大于 2 的偶数。

解决方案 19：

数字 1 是一个特殊情况，既不是质数也不是合数。有关更多信息，请访问： http: //mathworld.wolfram.com/PrimeNumber.html

并且，(n0.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' 开始减小......所以，最终我们要用小于平方根的数字来检查可整除性。

解决方案 20：

我有一个新的解决方案，我认为它可能比 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