检查质数，在 python。逻辑混乱

Question

我在一个检查素数的网站上找到这段代码

def isPrime(number):
    if (number <= 1):
        return False
    elif (number <= 3):
        return True
    elif (number % 2 == 0 or number % 3 == 0):
        return False
    
    i = 5
    while(i * i <= number):
        if (number % i == 0 or number % (i + 2) == 0):
            return False

        i += 6

    return True

但是看不懂while循环下if语句的逻辑，即if (number % i == 0 or number % (i + 2) == 0) 为什么需要 i+2？？？当 i 是偶数时，i+2 也是偶数和奇数，而 i 是奇数。那么，为什么需要检查 i+2???

Answer 1

i 从 5 开始，所以加 2 意味着只计算偶数。它使检查更快。

Answer 2

除了2和3，所有素数都是6n±1的形式。此代码明确检查 2 和 3，然后成对检查更大的数字：6n-1、6n+1，从 5 开始。因此它检查 5、7，然后是 11、13，然后是 17、19，依此类推。它在两对之间步进 6，在每对内步进 2。这样做可以避免检查 2 或 3 的倍数。

Answer 3

如果你想知道一个数是否是质数，这里有一个简短的例子

# Check if a positive integer number is a prime number. Check only till square root +1.

import math

def isPrime(n):
  if ( n > 3 ):
    if (n % 2 == 0):
      return False
    for i in range(3, math.isqrt(n), 2):
      if (n % i == 0):
        return False
    return True
  else:
    return True

检查质数，在 python。逻辑混乱

Check Prime Number, in python. logic confusion

python

primes

python-3.x