初等数论知识 — 筛素数、欧拉函数

文章目录

• • • 1.质数
    • • 1.1 质数的定义
      • 1.2 质数的判定
    • 2. 筛质数
    • • 2.1 Eratosthenes 筛法
      • 2.2 线性筛法
    • 3. 分解质因数
    • 4.约数
    • • 4.1 试除法求约数
      • 4.2 求1~N每个数的约数
    • 5.最大公约数、最小公倍数
    • • 5.1更相减损术
      • 5.2欧几里得算法
    • 6. 欧拉函数
    • • 6.1 求2～N中每个数的欧拉函数

1.质数

1.1 质数的定义

• 规定1不是质数也不是合数，n为质数的前提条件为（n >= 2&& $n\in N+$）
• 若n为质数，那么它只有1和它本身两个因子
• 特殊的，质数中只有一个偶数2，其他都是奇数

其他相关知识

• 对于一个整数N，[1,N]的质数大约有NlnN{N\over lnN}lnNN​个，即每$lnN$个数中有一个质数

1.2 质数的判定

试除法判定质数

• 1.暴力做法：
• 根据质数定义出发，暴力枚举区间[2,n-1]是否有其他因子，时间复杂度为$On)$，这里不再赘述

---

• 2.优化做法:
• 若一个合数为n，一个因子d∣n，那么一定有nd∣n若一个合数为n，一个因子d|n，那么一定有{n\over d}|n若一个合数为n，一个因子d∣n，那么一定有dn​∣n
• 因此，我们用只需要枚举最小的那个因子d就可以，d<=nd,d2<=n,d<=nd <= {n\over d},d^2<=n,d<=\sqrt{n}d<=dn​,d2<=n,d<=n​
• 枚举区间[2,n][2,\sqrt{n}][2,n​],时间复杂度为On)O\sqrt{n})On​)

代码如下:

bool is_primeint n){ifn < 2) return false;forint d = 2; d <= n/d; d ++ ){//如果d能整除n，那么n为合数ifn % d == 0) return false;}return true;
}

其他相关知识

• 有一些效率更高的随机性算法，例如“Miller-Robbin”等，有较小的概率把合数错误判定为质数，但多次判定合起来的错误趋近于零

2. 筛质数

问题：

给出一个整数N，求1~N之间所有质数

2.1 Eratosthenes 筛法

定义

• $任意整数x的倍数2x,3x,\dots \dots 都不是质数$
• $枚举[2,N],从小到大扫描每一个数，设这个数为x，则它的倍数2x,3x,......[N/x]\ast x都不是质数，标记为合数（这些合数就没有用了，遇到就跳过），当扫描到一个数x的时候，它前面[2,x-1]都已经扫描过了，如果当前这个数x没有被标记，这个数一定是质数$
• 小于x2的x的倍数在扫描更小的数已经被标记过（例如，前面x−1)能筛掉x−1)∗x）小于x^2的x的倍数在扫描更小的数已经被标记过（例如，前面x-1)能筛掉x-1)*x）小于x2的x的倍数在扫描更小的数已经被标记过（例如，前面x−1)能筛掉x−1)∗x）
• 因此减小枚举区间，从x2开始，筛去x2,x+1)∗x,……,N/x)∗x因此减小枚举区间，从x^2开始，筛去x^2,x+1)*x,……,N/x)*x因此减小枚举区间，从x2开始，筛去x2,x+1)∗x,......,N/x)∗x

时间复杂度计算

• 首先，引入一个概念：调和级数fn)=1+12+13+14+……+1n，当n趋于∞时，fn)=lnn)+γ（γ为欧拉常数）调和级数fn)=1+{1\over 2}+{1\over 3}+{1\over 4}+……+{1\over n}，当n趋于∞时，fn) = lnn)+γ（γ为欧拉常数）调和级数fn)=1+21​+31​+41​+……+n1​，当n趋于∞时，fn)=lnn)+γ（γ为欧拉常数）
• $筛素数：n/2+n/3+\dots \dots +n/n=nfn)-1)=nfn))-n$
• $由于，不超过N的质数大约N/lnN个，所以时间复杂度为ONlogNlogN)\approx ON)$

代码如下:

int primes[N],cnt;//存储质数
bool v[N];//标记合数void get_primesint n){forint i = 2; i <= n; i ++ ){ifv[i]) continue;primes[++cnt] = i;forint j = i; j <= n/i; j ++) v[j * i] = true;}
}

2.2 线性筛法

思想

• $使每一个合数只会被它最小质因子筛取，时间复杂度为On)$

问题引入：

• 通过上面埃氏筛法可以看到，时间复杂度接近线性，但是即使在优化后（从x2开始筛），也会重复标记合数通过上面埃氏筛法可以看到，时间复杂度接近线性，但是即使在优化后（从x^2开始筛），也会重复标记合数通过上面埃氏筛法可以看到，时间复杂度接近线性，但是即使在优化后（从x2开始筛），也会重复标记合数

Solution

• $从小到大枚举已经存储的质数，用一个数组存储每个数的最小质因子$

代码如下：

int primes[N],cnt;//存储质数
int v[N];//存储每个数的最小质因子void get_primesint n){cnt = 0;forint i = 2; i <= n; i ++ ){//如果v[i]=0,表示当前数为质数if!v[i]) v[i] = i,primes[++cnt] = i;//从小到大枚举所有已经存储过的质数,让i乘上这些质数forint j = 1; j <= cnt; j ++){//如果当前质数大于i的最小质因子或者i*primes[j]>n就终止ifprimes[j] > v[i] || primes[j] > n/i) break;//i*primes[j]的最小质因子就是primes[j]v[i*primes[j]] = primes[j];}}
}

3. 分解质因数

算数基本定理

• 任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：N=p1c1p2c2p3c3……pkck，其中p1<p2<p3<…<pk,ci均为正整数任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：N =p_1^{c_1}p_2^{c_2}p_3^{c_3}……p_k^{c_k}，其中p_1<p_2<p_3<…<p_k,c_i均为正整数任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：N=p1c1​​p2c2​​p3c3​​……pkck​​，其中p1​<p2​<p3​<...<pk​,ci​均为正整数
• 同样依据上面的试除法，枚举区间[2,n]，但如果d为n的质因子，同样依据上面的试除法，枚举区间[2,\sqrt{n}]，但如果d为n的质因子，同样依据上面的试除法，枚举区间[2,n​]，但如果d为n的质因子，nd也属于n的质因子，这个区间就不够，而这种情况只会出现一次。{n\over d}也属于n的质因子，这个区间就不够，而这种情况只会出现一次。dn​也属于n的质因子，这个区间就不够，而这种情况只会出现一次。因此，需要特判一下，n是否有这个大于n的质因子因此，需要特判一下，n是否有这个大于\sqrt{n}的质因子因此，需要特判一下，n是否有这个大于n​的质因子
• 反证法：如果出现两次，就会有两个质因子大于n,相乘大于n反证法：如果出现两次，就会有两个质因子大于\sqrt{n},相乘大于n反证法：如果出现两次，就会有两个质因子大于n​,相乘大于n
• $区间里面枚举的n的因子都是n的质因子，因为n的合数因子也是由这些质因子构成的，$$在枚举到合数因子之前它包含的质因子已经筛掉了。$

代码如下

int primes[N],cnt;//存储质数
int c[N];//存储质因子的次数void divideint n){cnt = 0;forint d = 2; d <= n/i; d ++ ){//这个d就是n的质因子ifn % d == 0){primes[++cnt] = d;//筛掉所有的d,并记录d出现的次数whilen%d == 0) n/=d,c[cnt]++;}}//如果n大于1.那么这个数就是唯一一个大于根号n的质因子ifn > 1) {primes[++cnt] = n,c[cnt] = 1}
}

拓展：PoLLard’s Rho算法

一个比试除法效率更高的质因数分解算法，暂不讨论

4.约数

约数的定义

• $若一个d能整除n，那么称d是n的约数，n是d的倍数，记为d|nd\in Z，n\in Z)$

算数基本定理的推论

• N>1且N∈Z，N的正约数集合为{p1b1p2b2pkbk},其中0<=bi<=ciN>1 且 N∈Z，N的正约数集合为\{p_1^{b_1}p_2^{b_2}p_k^{b_k}\},其中0<=b_i<=c_iN>1且N∈Z，N的正约数集合为{p1b1​​p2b2​​pkbk​​},其中0<=bi​<=ci​

---

$一、计算N的正约数个数$

• 根据推论可以得出，N的每一个质因子的次数可以出现0到ci次，那么N的正约数个数为（c1+1）∗c2+1)∗…∗ck+1)=∏i=1kci+1)根据推论可以得出，N的每一个质因子的次数可以出现0到c_i次，那么N的正约数个数为（c_1+1）*c_2+1)*…*c_k+1) = \prod_{i=1}^{k}c_i+1)根据推论可以得出，N的每一个质因子的次数可以出现0到ci​次，那么N的正约数个数为（c1​+1）∗c2​+1)∗...∗ck​+1)=∏i=1k​ci​+1)

代码如下：

unordered_map<int,int> primes; 
//first:质因子 second:质因子的次数forint i = 2; i <= n/i; i ++ ){whilen % i == 0){n/=i;primes[i]++;}
}
ifn > 1) primes[n]++;int res = 1;
forauto prime:primes) {res *= prime.second + 1);}

---

$二、计算N的所有正约数之和$

• 每个正约数都是由质因子组成，所有组合的约数之和可以表示为：p10+p11+p1c1)∗p20+p21+p2c2)∗…∗pk0+pk1+pkck)每个正约数都是由质因子组成，所有组合的约数之和可以表示为：p_1^{0}+p_1^{1}+p_1^{c_1})*p_2^{0}+p_2^{1}+p_2^{c_2})*…*p_k^{0}+p_k^{1}+p_k^{c_k})每个正约数都是由质因子组成，所有组合的约数之和可以表示为：p10​+p11​+p1c1​​)∗p20​+p21​+p2c2​​)∗...∗pk0​+pk1​+pkck​​)
• ★这里的公式很特别，用代码写的话，用一个变量t=pi0一次都没出现的情况),t=t∗pi+1)，可以写循环，时间复杂度O（n）★这里的公式很特别，用代码写的话，用一个变量t = p_i^0一次都没出现的情况),t = t *p_i + 1)，可以写循环，时间复杂度O（n）★这里的公式很特别，用代码写的话，用一个变量t=pi0​一次都没出现的情况),t=t∗pi​+1)，可以写循环，时间复杂度O（n）

代码如下：

unordered_map<int,int> primes; //first:质因子 second:质因子的次数forint i = 2; i <= n/i; i ++ ){whilen % i == 0){n/=i;primes[i]++;}
}
ifn > 1) primes[n]++;int res = 1;
forauto prime:primes) {int p = prime.first,c = prime.second;int t = 1;whilec --) t = t * p + 1;res *= t;
}

4.1 试除法求约数

求N的所有正约数

• 若d为n的约数，那么nd也是n的约数，所以约数总是成对出现，若d为n的约数，那么{n\over d}也是n的约数，所以约数总是成对出现，若d为n的约数，那么dn​也是n的约数，所以约数总是成对出现，与求质数一样，只需要枚举最小的约数d,1<=d<=n注意这里从1开始)，如果d=n,我们只需要特判一下，只要一个求质数一样，只需要枚举最小的约数d,1<=d<=\sqrt n注意这里从1开始)，如果d=\sqrt n,我们只需要特判一下，只要一个求质数一样，只需要枚举最小的约数d,1<=d<=n​注意这里从1开始)，如果d=n​,我们只需要特判一下，只要一个
• 推论：一个整数N的约数个数最多2N个推论：一个整数N的约数个数最多2\sqrt N个推论：一个整数N的约数个数最多2N​个

代码如下：

int factor[N],cnt;//存储约数void get_factorint n){forint d = 1; d <= n/d; d ++ ){ifn%d == 0){factor[++cnt] = d;//如果d*d!=nifd != n/d) factor[++cnt] = n/d;}}
}

4.2 求1~N每个数的约数

• 若使用上面的试除法，时间复杂度为O（NN）太高若使用上面的试除法，时间复杂度为O（N\sqrt N）太高若使用上面的试除法，时间复杂度为O（NN​）太高

---

• $这里采用倍数法，一个数的所有约数不好算，那么反过来思考，求1N的每个数d的倍数，d,2d,3d...,[N/d]\ast d它们的约数都是d$
• $时间复杂度为ON+N/2+N/3+...+N/N)\approx ONlogN)$
• $1到N每个数的约数个数的总和大约为NlogN个。$

代码如下

vector<int> factor[N];forint i = 1; i <= n; i ++ ){forint j = 1; j <= n/i; j ++ ){factor[i * j].push_backi);}
}forint i = 1; i <= n; i ++ ){forint j = 0; j < factor[i].size); j ++ ){printf"%d ",factor[i][j]);}puts"");
}

5.最大公约数、最小公倍数

最大公约数的定义

• $若d|a,d|b，则d是a和b的公约数，在所有公约数中取最大那个，称为a和b的最大公约数，记为gcda,b)$

最小公倍数的定义

• $若a|m,b|m,则m是a和b的公倍数，在所有公倍数中取最小那个，称为a和b的最小公倍数，记为lcma,b)$

三个数及以上，同理

公式
一、
∀a,b∈N,lcma,b)=a∗bgcda,b)\forall a,b\in \mathbb{N}, lcma,b) = {a*b\over gcda,b)}∀a,b∈N,lcma,b)=gcda,b)a∗b​

• 证明：设d=gcda,b),a0=a/d,b0=b/d,则gcda0,b0)=1,根据最小公倍数定义，lcma0,b0)=a0∗b0,lcma,b)=lcma0,b0)∗d=a0∗b0/d设d=gcda,b),a_0 = a/d,b_0=b/d,则gcda_0,b_0) = 1,根据最小公倍数定义，lcma_0,b_0) = a_0*b_0,lcma,b) =lcma_0,b_0)*d=a_0*b_0/d设d=gcda,b),a0​=a/d,b0​=b/d,则gcda0​,b0​)=1,根据最小公倍数定义，lcma0​,b0​)=a0​∗b0​,lcma,b)=lcma0​,b0​)∗d=a0​∗b0​/d

5.1更相减损术

公式
一、
$\forall a,b\in \mathbb{N},a>=b,有gcda,b)=gcdb,a-b)=gcda,a-b)$
二、
$\forall a,b\in \mathbb{N},有gcdxa,xb)=x\ast gcda,b)$

证明
a>=b,对于任意公约数d,因为d∣a,d∣b,a=[ad]∗d,b=[bd]∗d,a−b=[ad]−[bd])∗d,所以d∣a−b).因此，a,b公约数集合与b,a−b公约数集合相同，a,a−b同理a>=b,对于任意公约数d,因为d|a,d|b,a = [{a\over d}]* d,b = [{b\over d}]*d,a-b =[{a\over d}] – [{b\over d}])*d ,所以d|a-b).因此，a,b公约数集合与b,a-b公约数集合相同，a,a-b同理a>=b,对于任意公约数d,因为d∣a,d∣b,a=[da​]∗d,b=[db​]∗d,a−b=[da​]−[db​])∗d,所以d∣a−b).因此，a,b公约数集合与b,a−b公约数集合相同，a,a−b同理

5.2欧几里得算法

公式
$\forall a,b\in \mathbb{N},b\ne 0,gcda,b)=gcdb,a\mathrm{m}\mathrm{o}\mathrm{d}b)$

证明
$这里需要分类讨论a和b的大小情况$

• $若a<b,那么a\mathrm{m}\mathrm{o}\mathrm{d}b=a,gcdb,a\mathrm{m}\mathrm{o}\mathrm{d}b)=gcdb,a)=gcda,b)$
• $若a>=b,这上面更相减损术已经讨论过了，gcda,b)=gcdb,a-b),因为a-b=a\mathrm{m}\mathrm{o}\mathrm{d}b,gcda,b)=gcdb,a\mathrm{m}\mathrm{o}\mathrm{d}b)$

关于两种求最大公约数的方法

• $首先，我们清除的知道，求出gcd也就能算出lcm$
• $一般情况下，使用欧几里得算法，时间复杂度为Ologa+b))，若遇到高精度就用更相减损术（暂时没用过）$

欧几里得算法实现

int gcdint a,int b){//当b=0时，gcda,0)=aif!b){return a;}else{return gcdb,a%b);}
}

6. 欧拉函数

前置知识：互质
$\forall a,b\in \mathbb{N},若gcda,b)=1,则称为a和b互质，对于三个及以上个数，gcda,b,c)=1叫做a、b和c互质，gcda,b)=gcdb,c)=gcda,c)叫a,b,c两两互质。$

欧拉函数的定义
$1～N中与N互质数的个数叫欧拉函数，记为\varphi N)$

公式：
依据算术基本定理，若N=p1c1p2c2…pkck，则依据算术基本定理，若N=p_1^{c_1}p_2^{c_2}…p_k^{c_k}，则依据算术基本定理，若N=p1c1​​p2c2​​...pkck​​，则
ϕN)=N∗p1−1p1∗p2−1p2∗…∗pk−1pk=N∗∏质数p∣N1−1p)\phiN) = N * {p_1-1 \over {p_1}} * {p_2-1 \over {p_2}} *…*{p_k-1 \over {p_k}} = N *\prod_{质数p|N}1 – {1\over p})ϕN)=N∗p1​p1​−1​∗p2​p2​−1​∗...∗pk​pk​−1​=N∗∏质数p∣N​1−p1​)

证明：
$用到了容斥原理，参考《算法进阶指南》上的证明，设p、q是N的质因子，1到N中p的倍数有[N/p]个，$
同理，q的倍数有[N/q]个，剩下的有N−[N/p]−[N/q]个，但是这里把p和q的倍数减去两次（p的倍数一次，q的倍数一次），需要加上那么结果为N−Np−Nq+Npq=N∗1−1p)∗1−1q),同理得出全部与N互质的个数。同理，q的倍数有[N/q]个，剩下的有N-[N/p]-[N/q]个，但是这里把p和q的倍数减去两次（p的倍数一次，q的倍数一次），需要加上那么结果为N-{N\over p}-{N\over q} + {N\over pq} = N*1-{1\over p})*1-{1\over q}),同理得出全部与N互质的个数。同理，q的倍数有[N/q]个，剩下的有N−[N/p]−[N/q]个，但是这里把p和q的倍数减去两次（p的倍数一次，q的倍数一次），需要加上那么结果为N−pN​−qN​+pqN​=N∗1−p1​)∗1−q1​),同理得出全部与N互质的个数。

代码如下：

int phiint n){int ans = n;forint i = 2; i <= n/i; i ++ ){ifn % i == 0){ans = ans/i*i - 1);whilen % i == 0) n/=i;}}ifn > 1) ans = ans/n*n - 1);return ans;
}

6.1 求2～N中每个数的欧拉函数

• $根据欧拉函数的公式，我们可以先求出所有质数，前面有两种：埃氏筛法、线性筛法$
• $显然，质数p的欧拉函数：p-1，合数欧拉函数就先找到它的质因子，依次得出$

埃氏筛法求欧拉函数

int primes[N],cnt;//存储质数
int phi[N];//phi[i]:表示i的欧拉函数void eulerint n){//1的欧拉函数是1phi[1] = 1;forint i = 2; i <= n; i ++ ) phi[i] = i;forint i = 2; i <= n; i ++ ){//i是质数ifphi[i] == i){//对于j，多个i质因子forint j = i; j <= n; j += i){phi[j] = phi[j]/i*i - 1);}}}
}

线性筛法求欧拉函数
$若i\mathrm{m}\mathrm{o}\mathrm{d}pj==0,\varphi i\ast pj)=\varphi i)\ast pj$
否则，ϕi∗pj)=ϕi)∗pj∗1−1pj)=ϕi)∗pj−1)否则，\phii*pj) = \phii)*pj*1-{1\over pj}) = \phii)*pj – 1)否则，ϕi∗pj)=ϕi)∗pj∗1−pj1​)=ϕi)∗pj−1)

int primes[N],cnt;//存储质数
int st[N];//st[i]:i的最小质因子
int phi[N];//phi[i]:表示i的欧拉函数void eulerint n){forint i = 2; i <= n; i ++ ){if!st[i]) st[i] = i,primes[++cnt] = i,phi[i] = i - 1;forint j = 1; j <= cnt; j ++ ){ifprimes[j] > st[i] || primes[j] > n/i) break;//i*primes[j]的最小质因子primes[j]st[i*primes[j]] = primes[j];//如果primes[j]是i的最小质因子,说明i*primes[j]已经有这个质因子ifi % primes[j] == 0){phi[i*primes[j]] = phi[i] * primes[j];}else{//primes[j]是新成员phi[i*primes[j]] = phi[i] * primes[j] - 1);}}}
}

后记：以上笔记是本人参考《算法进阶指南》书籍以及之前所学总结而得，如果知识不完善或者有误，请各位指点。如果对您有帮助，点赞，关注共同进步