Question

使用加法，彻底分解数字

例如 5 = 1 + 1 + 1 + 1 + 1。

不可分解的单元是 1。不稀奇。

使用乘法，彻底分解数字

加法换成乘法之后，事情变化多端，例如 5 = 5，例如 6 = 2 × 3。可以发现，2、3、5、7、11 等，是不可分解的单元。至于 4、6、8、9、10 等，可以再分解。

不可分解的单元叫做“质数”！非常稀奇！

接下来要介绍的演算法有：从小到大列出质数（建立质数表）、判断一个数是不是质数（质数测试）、使用乘法凑得给定的数（质因数分解）。

Prime Generation: Sieve of Eratosthenes

Sieve of Eratosthenes

这是一个制作质数表的演算法。简称“筛法”。

列出所有正整数。从 2 开始，删掉 2 的倍数。找下一个未被删掉的数字，找到 3，删掉 3 的倍数。找下一个未被删掉的数字，找到 5，删掉 5 的倍数。如此不断下去，就能删掉所有合数，找到所有质数。

质数有无限多个，证明省略。我们无法找到所有质数，通常是预先订立一个范围，只找到范围内的所有质数。

Prime Generation: Segmented Sieve of Eratosthenes

Segmented Sieve of Eratosthenes

筛法当中，以不大于 sqrt(N) 的质数，筛选大于 sqrt(N) 的数。有种洞烛机先、以小搏大的味道。

筛法需要大量记忆体空间。为了节省记忆体空间，于是有了分段处理的手法：一、首先求得不大于 sqrt(N) 的质数。二、将记忆体切成小段，每段长度 sqrt(N)。分别筛选每一段。

空间複杂度从 O(N) 变成 O(sqrt(N))，大幅减少 cache miss。

也许可以做为平行演算法的经典范例。

Prime Generation: Linear Sieve Algorithm

线性时间筛法

一边制作质数表，一边删掉每个数的质数倍，如此每个合数就只读取一次，时间複杂度达到 O(N)。

Prime Generation: Wheel Factorization

6n±1 Method

这是一个精简版的筛法，原理是：只拿 2 和 3 这两个质数先筛过一遍，剩下的数字则用试除法验证是不是质数。

2 和 3 的最小公倍数是 6，我们就把所有数字分为 6n、6n+1、6n+2、6n+2、6n+3、6n+4、6n+5 六种（n 是倍率）。除以六会馀零的数字为 6n，除以六会馀一的数字为 6n+1，以此类推。

可以看出 6n、6n+2、6n+3、6n+4 会是 2 或 3 的倍数，不属于质数。因此，只要验证 6n+1 和 6n+5 是不是质数就可以了。（6n+5 也可以写成 6n-1，意义不变。）

6n-1 到 6n+1，再到下一个 6n-1，再到 6n+1，把这些要验证的数字由小排到大，可以发现之间的差值会是 2 4 2 4 2 4 ...不断跳二跳四。实作程式码时，就可以直接用加法加二加四，而不必用乘法及加减法计算 6n-1、6n+1，如此一来程式的执行效率会好一点。

验证的顺序是：数字 2 和 3 明显的是质数，不必验证；若是从数字 5 开始验证，那麽下一个要验证的数字就是 5+2，再下一个就是 5+2+4，再下一个就是 5+2+4+2，如此不断下去。

Primality Test

Primality Test

质数测试，测试一个数字是否为质数。

质数测试属于 P 问题，不过以下介绍的皆非多项式时间的演算法，甚至是不保证结果正确的演算法。若对多项式时间、保证结果正确的演算法有兴趣，可上网搜寻 AKS Algorithm。

要进行质数测试，可以直接运用筛法建立质数表，再来判断质数。然而建立质数表需要大量记忆体，因此又发明了其他方法。

Divisibility Primality Test

整除性测试法。依照质数定义，一个质数 p 不会被大于 1 且小于 p 的数字整除，只要把这些数字都拿来试除，就可以判定一个数字是不是质数。

此演算法其实就是穷举所有可能的因数一一试除。

Primality Test: Miller-Rabin Algorithm

演算法

结合 Square Root Primality Test 与 Fermat's Primality Test。

此演算法的结果不一定正确。通过测试的数字，可能是合数或质数；无法通过测试的数字，一定是合数。

一、选定一个底数 a，大于 1、小于 n，用来进行费玛测试。
　　待测数字 n，会是费玛测试的模数。
二、令 n-1 = u * 2^t，其中 t 尽量大（u 为奇数）。
三、观察 a^u 这个数字：
　　若等于±1，
　　则表示步骤四，所有数字都是 1，永不出现平方根测试的反例。
　　也表示步骤五，最终将通过费玛测试。
　　推定 n 是质数。
四、依序观察 a^(u * 2^1)、a^(u * 2²)、…、a^(u * 2^(t-1)) 这些数字，
　　每个数字正好是前一个数字的平方：
　甲、一旦发现有个数字的平方等于+1，
　　　则表示无法通过平方根测试。
　　　（但是步骤五，最终将通过费玛测试。）
　　　确定 n 是合数。
　乙、一旦发现有个数字的平方等于-1，
　　　则表示接下来的数字都是 1，永不出现平方根测试的反例。
　　　也表示步骤五，最终将通过费玛测试。
　　　推定 n 是质数。
五、观察 a^(u * 2^t) 这个数字：
　甲、若等于+1，表示通过费玛测试，推定 n 是质数。
　乙、若不等于+1，表示无法通过费玛测试，确定 n 是合数。
　回、也就是说，a^(u * 2^(t-1)) 必须等于±1，平方之后才会等于+1。
　　　步骤五才能通过费玛测试。
　回、由于步骤四已经检查过 a^(u * 2^(t-1)) 是否为±1，
　　　所以步骤五可以省略，直接确定 n 是合数。

Integer Factorization

Integer Factorization

把一个正整数分解成质因数的连乘积。

n = 2^n1 * 3^n2 * 5^n3 * 7^n4 * 11^n5 * …

Factor 是“因式”。Factorization 是“因式分解”。Integer Factorization 是“因式分解的对象为整数”，译作“整数分解”。另外，中学课本译作“质因数分解”，著眼于分解结果而非分解对象。

质因数分解属于 NP 问题，但是目前还不确定它究竟是 P 问题或是 NP-complete 问题，相当特别。

Fundamental Theorem of Arithmetic（算术基本定理）

凡是正整数都可以藉由质因数分解成为一个独一无二的式子，不同的 n 就会对应不同的(n1, n2, …)，反方向亦同。

根据算术基本定理，凡是牵扯到乘法、因数、倍数的数学运算，都可以改变成比较简单的运算。

分解前     | 分解后
n          | (n1, n2, ...)
m          | (m1, m2, ...)
-----------+--------------------------------------
乘除法     | 加减法
n × m      | (n1 + m1, n2 + m2, ...)
n ÷ m      | (n1 - m1, n2 - m2, ...)
           |
整除       | 大于等于
n % m = 0  | (n1, n2, ...) ≥ (m1, m2, ...)
m | n      | n1≥m1 and n2≥m2 and ...
           |
最大公因数 | 最小值
gcd(n, m)  | (min(n1, m1), min(n2, m2), ...)
           |
最小公倍数 | 最大值
lcm(n, m)  | (max(n1, m1), max(n2, m2), ...)
           |
互质       | 对应项必须有零
n ⊥ m     | min(n1, m1) = 0 and min(n2, m2) = 0 and ...
           | n1*m1 = 0 and n2*m2 = 0 and ...

算术基本定理阐述了另一种世界观，把数字看作是质数的结合。质数的英文 prime 有著“原始就有”的意思，便是指质数是所有数字的根本。

UVa 11889

Trial Division Factorization Method

把所有可能的因数拿来试除。用质因数会更好；可以预先建立质数表。

Integer Factorization: Pollard's ρ Algorithm

乱数产生器

此演算法可以找到 n 的其中一个因数。

使用一个简单的乱数产生器 f(aᵢ₊₁) = aᵢ² + c (mod n)，尝试各种 a₀与 c，制造所有可能的因数，一一试除即可。

以此乱数产生器公式，依序枚举 a₀、a₁、a₂、……，模 n 的情况下，最终必定循环。绘图时可以画成一个ρ的形状，演算法因而得名。ρ唸作[ro]，可以写作 rho。

运用最大公因数找到因数

因为乱数产生器制造的数字 a，a 恰是 n 的因数的机会较小，而 a 与 n 有共同因数的机会较大，所以改用 d = gcd(a, n) 来找到 n 的因数 d。最大公因数有著极快的演算法，对执行速度影响不大。

侦测循环

乱数产生器最终必会出现重覆数字，产生循环。一旦遇到循环，立刻结束枚举，不再进行重覆运算。

另外，此演算法改用 abs(a_x - a_y)，用数字的差值制造所有可能的因数。我不知道如此做的原因。

原论文採用“ Floyd's Algorithm ”侦测循环。

Integer Factorization: Quadratic Sieve Algorithm

Fermat's Factorization Method

一个数字 n，分解成两个数 x y 的乘积。

运用平方差公式，令 n = a² - b² = (a+b) (a-b) = x y。寻找刚好相差 n 的两个平方数 a²与 b²，就能分解 n。

实作程式码时，穷举整数 a，然后推导出 b = sqrt(a² - n)，判断 b 是不是整数。

Euler's Totient Function

Euler's Totient Function（Euler's φ Function）

这是一个公式。计算 1 到 n 的正整数当中，跟 n 互质（最大公因数是一）的数，总共有几个。

首先要将 n 做质因数分解：

n = p₁a₁ × p₂a₂ × … × pₖaₖ   where p₁ … pₖ are primes

以质因数计算 Euler's Totient Function。φ唸做[fai]，可以写做 phi：

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … × (1 - 1/pₖ)

可以採用这个顺序计算，避免溢位：

n ÷ p₁ × (p₁-1) ÷ p₂ × (p₂-1) ÷ … ÷ pₖ × (pₖ-1)

如此就不用一个一个去计算最大公因数了，非常有效率！

质因数分解採用试除法，计算 Euler's Totient Function 的时间複杂度为 O(sqrtN)。预先建立质数表，得加速至 O(π(sqrtN))，其中π(N) 是 1 到 N 的质数个数。

UVa 10299 10179 11064

性质

φ(p) = p - 1                  iff p is prime.
φ(pa) = pa - pa-1              iff p is prime.
φ(n × m) = φ(n) × φ(m)        iff n and m are relatively prime.
φ(n) = φ(p₁a₁) × … × φ(pₖaₖ)   iff n = p₁a₁ × … × pₖaₖ
                              where p₁ … pₖ are prime.

建立表格

未经改良的筛法，能求出每个数的质因数。运用筛法计算 Euler's Totient Function，时间複杂度为 O(NloglogN)。

Möbius Function

Möbius Function

用排容原理求一个数字的所有因数总和。

ICPC 2116