关于质数（素数）-白红宇

什么是质数？

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

算术基本定理

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

素数定理

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

试除法

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

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

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

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

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复制代码

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

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复制代码

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

筛选法

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

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

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复制代码

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

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复制代码

费马小定理

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

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

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

import randomdef gcd(a, b):    while b != 0:        a, b = b, a % b    return adef 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 ansdef 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复制代码