质数

如果一个数只能被$1$和它本身整除，那么这个数就称为质数，又称素数，否则称为合数.

判断一个数是否为质数

试除法判断一个数是否为质数

注意到如果有$n \bmod i = 0$，则$n = i\times c$，其中$c = \frac{n}{i}$为一非零整数。换句话说，如果有$n \bmod i = 0$，则一定有唯一的$c$使得$c \times i = n$.

不妨称$<i, c>$是$n$的一个因子对，则在$i \in [2, n]$中，如果$<i, c>$是$n$的一个因子对，由乘法交换律知$<c, i>$也一定是$n$的一个因子对，反过来，如果$<i, c>$不是$n$的一个因子对，则$<c, i>$也一定不是$n$的一个因子对。不妨假设$i < n$，则我们只需判断在$i \in [2, \lfloor\frac{n}{i}\rfloor]$中，$n \bmod i = 0$是否成立即可.

def is_prime(n):
	if n < 2:
        return False
    i = 2
    while i <= n // i:
		if n % i == 0:
			return False
    	i += 1
    return True

时间复杂度恒为$O(\sqrt n)$

分解质因数

由质数的定义我们知道，每一个数都可以分解为若干质数的乘积。即

$$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \cdots p_k^{\alpha_k}$$

其中$p_i$表示第$i$个质数，$\alpha_i$表示在这个分解因式中第$i$个质数出现的次数(即它的幂次)。分解质因数问题需要我们求出给定数$n$的所有质数和它们的幂次.

试除法分解质因数

通过枚举$i \in [2, n]$中的每一个数，并判断每个数是否为质因子。该代码能够枚举出所有可能的质因子，而不会出现任何的合数。我们可以用反证法来证明这一点：

假设一个合数$i(\ge 2)$满足$n \bmod i = 0$，则一定有合数$i$的一个质因子$p$满足$n \bmod p = 0$，且$p < i$严格成立，由于$i$是从小到大枚举的，故原假设不成立.

在这份代码中我们需要特判，如果$n$本身就是质数，则它的所有质因子只有它本身，幂次为$1$.

def division(n):
	i = 2
    while i <= n // i:
        # 从小到大枚举每一个质数
        if n % i == 0:
            # 判断是否为质因子,避免输出s为0的情况
            s = 0
            while n % i == 0:
                # 计算该质因子的幂次
                n //= i
                s += 1
            print(i, s)
    	i += 1
    if n > 1:
        # 如果n本身就是一个质数
		print(n, 1)

时间复杂度为$O(n \log n)$

筛质数

给定一个数$n$，求出不大于$n$的数中的所有质数。

朴素法筛质数

我们可以遍历不大于$n$的每一个数，并判断这个数是否是质数。在判断之前，我们可以筛去所有的合数。

简单来说，当我们枚举到第$j$个数的时候，如果这个数能够被一个质数整除，那么这个数就一定是合数。注意到如果存在$j \bmod i = 0$，则$i <= j,(j \ge 0)$，事实上我们可以在存储第$i$个数时就把第$j$个数筛去，因为第$j$个数是以$i$为因子的一个合数。只需添加更新代码，当$j \in (i,n]$且$j \bmod i = 0$时，$j$一定不是质数，执行语句st[j] = True.

事实上，我们可以保证在更新过程中，$i$一定是一个质数。这是因为每一个合数都可以由比它小的质数相乘得来，而枚举始终是从小到大的顺序，如果第$j$个数是合数，在枚举到它之前，它就已经被筛去了。

primes = [0] # 用于存储所有的质数
st = [False]*n # 储存第i个数被筛的状态，初始时均未被筛

def get_primes(n):
    for i in range(2, n+1):
        if st[i-1]:
            continue
        primes.append(i)
        for j in range(i+i, n+1, i):
            st[j-1] = True

时间复杂度约为$O(n\log\log n)$

线性筛法筛质数

在朴素筛法中，对于每一个数，我们都将以该数作为因子的所有数筛去，但显然这样存在重复的操作。我们可以进一步优化代码。我们重新规定筛法：如果一个数可以被筛，那么它一定是被它的最小质因子筛去的。这样做可以确保每个数只被筛一次。

如何保证每个合数只被最小质因子筛去呢？假设当前枚举到第$i$个数

• 如果这个数没有被筛去，则存入$primes$数组
• 遍历当前存在的每一个质数
  • 如果i % primes[j] == 0成立，说明$primes[j]$是$i$的最小质因子(因为$j$是从小到大遍历的），同时$primes[j]$是$primes[j]*i$的最小质因子
  • 否则，说明$primes[j]$比$i$的最小质因子要小，同时$primes[j]$是$primes[j]\cdot i$的最小质因子
• 执行st[primes[j] * i - 1] = True，因为无论如何$primes[j] \cdot i$的最小质因子都是$primes[j]$

如何证明这个算法能筛去所有合数？因为我们确保了每一个数的筛与不筛都是从小到大的顺序，如果一个数$i = x$是合数，那么它一定满足x % primes[j] == 0，其中$primes[j]$ 是$i$的最小质因子，令$ x \div primes[j] = m$ ，必定有 $m < x$ ，即该合数一定会在$i = m$时执行语句st[primes[j] * m - 1] = True，则该合数一定会被筛去。

def get_primes(n):
    primes = []  # 用于存储所有的质数
    isCombine = [False] * (n + 1)  
    # 储存第i个数被筛的状态，初始时均未被筛
    for i in range(2, n + 1):
        # 如果当前数是质数
        if not isCombine[i]: primes.append(i)
        j = 0
        while i <= n // primes[j]:
            # primes[j] * i 一定是合数
            isCombine[primes[j] * i] = True
            if i % primes[j] == 0:
                # i的最小质因子是primes[j]，不能再筛
                break
            # 筛下一个质数
            j += 1
    return primes

时间复杂度为$O(n\log \log n)$

约数

求一个数的所有约数

与求质数类似，对于一个整数$n$，如果存在$i \in [1, n]$有$n \bmod i = 0$，则$i$是$n$的一个约数，同时$n \div i$也是$n$的一个约数，因此我们只需要枚举到$i <= \frac{n}{i}$即可.

注意存入约数时如果存在$i * i = n$，则$i$应该只被存储一次，所以在每次存入$\frac{n}{i}$时，需要特判该数是否与$i$相等.

def get_divisons(n):
    ans = [] # 记录所有的约数
    i = 1
    while i <= n // i:
        if n % i == 0:
            ans.append(i)
            if i != n // i:
                ans.append(n // i)
        i += 1
    return sorted(ans)

对结果排序即可得到有序的约数集，但由于一个数的约数数量远比这个数本身小得多，最终时间复杂度为$O(\sqrt n)$

约数个数

给定一个整数$n$，求出它所有约数的个数。

在分解质因数中，我们已经知道，对于整数$n$，它一定可以分解成若干个质数的乘积，也即：

$$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \cdots p_k^{\alpha_k},$$

注意到对于$n$的第$j$个约数$d_j$，我们可以将其表示成

$$d_j = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdot p_3^{\beta_3} \cdots p_k^{\beta_k}, \quad\quad 0 \le \beta_i \le \alpha_i$$

并且由于是质数的乘积，对于任意两组不同的$\beta_1,\beta_2\,\beta_3,\cdots \beta_k$，它们所组成的约数也一定不同。于是求约数的个数可以转化为求这样一个排列的组合，对于第$i$项，$\beta_i$可取$[0, \alpha_i]$中的任意一个数，共$\alpha_i + 1$种可能。根据分步乘法原理，所有约数的个数$cnt$满足

$$cnt = (\alpha_1 + 1)(\alpha_2 + 1)(\alpha_3 + 1)\cdots(\alpha_k + 1).$$

def division_cnt(n):
    cnti = set() # 保存每一个质数和它的幂次
    # n本身就是它的一个约数
    ans = 1
    i = 2
    while i <= n // i:
        # 保存当前质数的幂次
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        cnti.add((i, cnt))
        i += 1
    
    # 需要特判，如果最终n不是1，说明这个数是一个质数
    # (且为n的所有约数中最大的有一个)
    if n > 1:
        cnti.add((n, 1))
    for p, a in cnti:
        ans *= a+1
    return cnti, ans

时间复杂度为$O(\sqrt n)$.

约数之和

给定一个整数$n$，求出它所有约数的和。

由上述约数性质可知，对于每一个组合$p_1^{\beta_1},p_2^{\beta_1},p_1^{\beta_1},\cdots p_1^{\beta_1}$，它能够构成$n$的一个约数，我们只需要将所有的约数相加即可。即约数之和$Sum$满足

$$Sum = \prod_{j = 1}^{k}\sum_{\beta_i = 1}^{\alpha_i} p_j^{\beta_j}, \quad\quad\beta_i \in [1, \alpha_i]$$

也即

$$Sum = (p_1^0 + p_1^1 + p_1^2 +\cdots + p_1^{\alpha_1})\cdots(p_k^0 + p_k^1 + p_k^2 +\cdots + p_k^{\alpha_k}).$$

对此如有疑惑，将上式展开则豁然开朗。

def division(n):
    cnti = set()
    ans = 1
    i = 2
    while i <= n // i:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        cnti.add((i, cnt))
        i += 1
    
    if n > 1:
        cnti.add((n, 1))
    res = 1
    for p, a in cnti:
        t = 1
        for _ in range(a):
            # 求(p^0 + p^1 +... + p^a)
            t = t*p + 1
        res *= t
    return res

时间复杂度为$O(\sqrt n)$.

辗转相除法求最大公约数

给定两个数$n, m$，求出它们的最大公约数。

性质：如果$d | a$且$d | b$，那么$d | (ax+by)$，其中$x,y$是整数，则有结论：$a$和$b$的最大公约数$gcd(a, b)$等价于$b$和$a \bmod b$的最大公约数$gcd(b, a \bmod b)$。

证明：设$gcd(a,b) = d$，$a \bmod b = a - c\cdot b$，其中$c$ 为一整数。则有$d|a,d|b$，$gcd(b, a \bmod b) = gcd(b, a - c\cdot b)$，由性质可知，$d | (a-c\cdot b)$，因此$gcd(a, b) = gcd(b, a-c\cdot b)$.

另一方面，如果$gcd(a,b) = d$，则$d|a,d|b$，则有$d | (ax+by)$，令$x = 0,y = -c$，则$d|(a- c\cdot b)$，即$gcd(b, a-c\cdot b) = gcd(a, b) = d$.

证毕

def gcd(a, b):
    return gcd(b, a % b) if b > 0 else a