文章目录
  1. 1. 质因数分解
    1. 1.1. 方法及证明
    2. 1.2. 复杂度的证明

引言:喵老板昨天睡前又教了我一手。喵老板是真的强。


质因数分解

算术基本定理:任何大于1的自然数,都可以表示成有限个素数(可以重复)的乘积,并且如果不计次序的话,表法是唯一的。

根据算数基本定理,我们可以将任意的数拆成小于它的素数的乘积,记pip_i为素数。

a=p1a1p2a2...pkaka=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}

那么如何得到这个分解呢?

方法及证明

我们可以在O(n)O(\sqrt n)的复杂度下得到一个数的质因数分解。

当我们使用i[2,n],i=i+1i\in [2,\sqrt n],i=i+1去除这个数时,如果可以整除,则继续用ii除,直到剩下的数不能整除ii。根据筛法特性,每个可用作整除的ii必定是质数,也就是pip_i,整除的次数就是aia_i

最终我们会得到剩下的数要么等于1,要么等于一个属于区间(n,n](\sqrt n,n]的质数。

证明:记剩下的数为kk,当k\not =1时,显然k(n,n]k\in (\sqrt n,n]

如果kk不是质数,则一定可因数分解为两个数a,ba,b,且有akn  or  bkna\leqslant \sqrt k \leqslant \sqrt n ~~or~~ b\leqslant \sqrt k \leqslant \sqrt n。再将a或b质因数分解,得到的质因数也一定小于等于根号n,也就是说k必定有一个质因数是小于等于根号n的(A)。又由于k是剩下的数,所以k不能被任何小于等于根号n的数整除(B),推出A和B矛盾。

因此k是质数,且k(n,n]k\in (\sqrt n,n]

复杂度的证明

证明复杂度为O(n)O(\sqrt n)

显然一个数n最多可被除O(log2n)O(log_2n)次,最少可被除O(lognn=1)O(log_nn=1)次,分别是使用最小的因数(除了1)和最大的因数进行除法运算。根据换底公式,我们不介意log的底是多少,因为常数忽略。所以除法的运算量是O(logn)O(logn)的。

而根据上面的方法,我们要用n\sqrt n个数去尝试除这个数,所以复杂度是O(n+logn)=O(n)O(\sqrt n+logn)=O(\sqrt n)的。

文章目录
  1. 1. 质因数分解
    1. 1.1. 方法及证明
    2. 1.2. 复杂度的证明