关于质数（素数）

什么是质数？

质数(Prime number)又称素数, 质数是大于111而且只能被111和自身整除的自然数。大于111的自然数如果不是素数，就称为合数(Composite number)。

算术基本定理

算术基本定理最早由欧几里得证明, 是表示任何合数都可以不断分解成素数的组合，如108108108可以分解为2，32，32，3两个素数，欧几里得发现把这些素数因子的次方相乘可以得到原来的数字108=22×33108=2^2×3^3108=22×33，而且这种分解为素数乘积的方式是唯一的。素数因子分解就像是一个锁，而且只有一把开锁的钥匙，这也是现代密码学的基础。

素数定理

素数定理描述素数在自然数中分布的渐进情况，就是小于nnn中素数的个数随着nnn的增大素数的密度就越来越小。当nnn越来越大时它的图像就越来越接近xln(x)\frac{x}{ln(x)}ln(x)x​。所以一个数字内素数的数量xxx约等于xln(x)\frac{x}{ln(x)}ln(x)x​，当xxx越大时误差越小。所以比如要生成sss大小的素数序列，使用这个方法的话就要提高反推出来上界xxx的大小。

试除法

那么怎么判断一个数是不是素数？这也是很多面试题里面问到的。一种简单的方法是试除法。

比如判断nnn是不是素数，可以让nnn除以111到nnn之间的整数，如果可以除尽则表示是合数否则是质数。

def isPrime(n):
    if n < 2: return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

但是可以发现大于222偶数都不是质数，因为它们可以被222整除，所以这可以减少迭代次数。

def isPrime(n):
    if n == 2: return True
    if n < 2 or n % 2 == 0: return False
    for i in range(3,n,2):
        if n % i == 0:
            return False
    return True

还有没有更快的方法？有，就是迭代到n\sqrt{n}n​，因为一个数字分解为两个因子，其中必然有一个小于或等于n\sqrt{n}n​，不然两个都大于n\sqrt{n}n​它们相乘就大于nnn了。

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

试除法还能不能更快？根据算术基本定理任何合数最终都可以分解为素数的组合，所以只用除小于nnn的素数就行了。

筛选法

筛选法（sieve of Eratosthenes）可以给出小于nnn的素数序列，比如要生成100100100内的素数序列，首先可以生成2到100间数字表，然后将列表第一个没被标记的数字标记为素数然后将数字表中它的倍数标记为合数，然后不断重复这个步骤。

对于给定nnn只需要遍历到n\sqrt nn​，剩下的就都是素数了。

def sieve(n):
    composite = {}
    primes = [2]

    for i in range(3, int(n ** 0.5) + 1, 2):
        if i not in composite:
            for j in range(i ** 2, n + 1, i): composite[j] = 1
    for k in range(3, n + 1, 2):
        if k not in composite: primes.append(k)

    return primes

对于不指定nnn的大小可以这么写。

def genPrimes():
    primes = [2]
    i = 1
    yield 2
    while True:
        i += 2
        for p in primes:
            if i % p == 0:
                break
        else:
            primes.append(i)
            yield i

费马小定理

虽然一般判断是不是素数用试除法就行了，但是当要判断一个大数是不是素数时，也还是太慢了。

费马小定理是欧拉定理的一个特殊情况，它是说一个正整数aaa的质数ppp次方减aaa可以被ppp次方整除。用公式表示可以为ap−1≡1 (mod p)a^{p-1} \equiv 1\ (mod\ p)ap−1≡1 (mod p)。

但是也不能完全正确，比如227561−1≡1 (mod 561)227^{561-1} \equiv 1\ (mod\ 561)227561−1≡1 (mod 561) 但是561=3×11×17561=3×11×17561=3×11×17，所以可以随机生成多个aaa来测试，这样就可以降低将出错概率。

import random
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def randA(p):
    return random.randint(1, p - 1)
def fastMod(f, p, m):
    ans = 1
    whlie p > 0:
        if p % 2 == 1:
            ans = (ans * f) % m
            p -= 1
        p //= 2
        f = (f ** 2) % m
    return ans
def isPrime(p):
    trials = 30
    for i in range(trials):
        a = randA(p)
        if gcd(a, p) != 1: return False
        if fastMod(a, p - 1, p) != 1: return False
    return True