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

文章目录

- - 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}$ 个，即每 $l n N$ 个数中有一个质数

1.2 质数的判定

试除法判定质数

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

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

代码如下:

bool is_prime(int n){if(n < 2) return false;for(int d = 2; d <= n/d; d ++ ){//如果d能整除n，那么n为合数if(n % d == 0) return false;}return true;
}

其他相关知识

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

2. 筛质数

问题：

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

2.1 Eratosthenes 筛法

定义

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

时间复杂度计算

首先，引入一个概念： $调和级数f(n)=1+12+13+14+……+1n，当n趋于∞时，f(n)=ln(n)+γ（γ为欧拉常数）调和级数f(n)=1+{1\over 2}+{1\over 3}+{1\over 4}+……+{1\over n}，当n趋于∞时，f(n) = ln(n)+γ（γ为欧拉常数）$
$筛素数： n / 2 + n / 3 + \dots \dots + n / n = n (f (n) - 1) = n (f (n)) - n$
$由于，不超过 N 的质数大约 N / l n N 个，所以时间复杂度为 O (N l o g N l o g N) \approx O (N)$

代码如下:

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

2.2 线性筛法

思想

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

问题引入：

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

Solution

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

代码如下：

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

3. 分解质因数

算数基本定理

$任何一个大于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均为正整数$
$同样依据上面的试除法，枚举区间[2,n]，但如果d为n的质因子，同样依据上面的试除法，枚举区间[2,\sqrt{n}]，但如果d为n的质因子，$ $nd也属于n的质因子，这个区间就不够，而这种情况只会出现一次。{n\over d}也属于n的质因子，这个区间就不够，而这种情况只会出现一次。$ $因此，需要特判一下，n是否有这个大于n的质因子因此，需要特判一下，n是否有这个大于\sqrt{n}的质因子$
$反证法：如果出现两次，就会有两个质因子大于n,相乘大于n反证法：如果出现两次，就会有两个质因子大于\sqrt{n},相乘大于n$
$区间里面枚举的 n 的因子都是 n 的质因子，因为 n 的合数因子也是由这些质因子构成的，$ $在枚举到合数因子之前它包含的质因子已经筛掉了。$

代码如下

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

拓展：PoLLard’s Rho算法

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

4.约数

约数的定义

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

算数基本定理的推论

$N>1 且 N∈Z，N的正约数集合为\{p_1^{b_1}p_2^{b_2}p_k^{b_k}\},其中0<=b_i<=c_i$

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

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

代码如下：

unordered_map<int,int> primes; 
//first:质因子 second:质因子的次数for(int i = 2; i <= n/i; i ++ ){while(n % i == 0){n/=i;primes[i]++;}
}
if(n > 1) primes[n]++;int res = 1;
for(auto prime:primes) {res *= (prime.second + 1);}

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

$每个正约数都是由质因子组成，所有组合的约数之和可以表示为：(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})$
$这里的公式很特别，用代码写的话，用一个变量t = p_i^0(一次都没出现的情况),t = (t *p_i + 1)，可以写循环，时间复杂度O（n）$

代码如下：

unordered_map<int,int> primes; //first:质因子 second:质因子的次数for(int i = 2; i <= n/i; i ++ ){while(n % i == 0){n/=i;primes[i]++;}
}
if(n > 1) primes[n]++;int res = 1;
for(auto prime:primes) {int p = prime.first,c = prime.second;int t = 1;while(c --) t = t * p + 1;res *= t;
}

4.1 试除法求约数

求N的所有正约数

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

代码如下：

int factor[N],cnt;//存储约数void get_factor(int n){for(int d = 1; d <= n/d; d ++ ){if(n%d == 0){factor[++cnt] = d;//如果d*d!=nif(d != n/d) factor[++cnt] = n/d;}}
}

4.2 求1~N每个数的约数

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

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

代码如下

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

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

最大公约数的定义

$若 d ∣ a, d ∣ b ，则 d 是 a 和 b 的公约数，在所有公约数中取最大那个，称为 a 和 b 的最大公约数，记为 g c d (a, b)$

最小公倍数的定义

$若 a ∣ m, b ∣ m, 则 m 是 a 和 b 的公倍数，在所有公倍数中取最小那个，称为 a 和 b 的最小公倍数，记为 l c m (a, b)$

三个数及以上，同理

公式
一、
$∀a,b∈N,lcm(a,b)=a∗bgcd(a,b)\forall a,b\in \mathbb{N}, lcm(a,b) = {a*b\over gcd(a,b)}$

证明： $设d=gcd(a,b),a_0 = a/d,b_0=b/d,则gcd(a_0,b_0) = 1,根据最小公倍数定义，lcm(a_0,b_0) = a_0*b_0,lcm(a,b) =lcm(a_0,b_0)*d=a_0*b_0/d$

5.1更相减损术

公式
一、
$∀a,b∈N,a>=b,有gcd(a,b)=gcd(b,a−b)=gcd(a,a−b)\forall a,b \in \mathbb{N},a>=b,有gcd(a,b) = gcd(b,a-b)=gcd(a,a-b)$
二、
$∀a,b∈N,有gcd(xa,xb)=x∗gcd(a,b)\forall a,b \in \mathbb{N},有gcd(xa,xb) =x*gcd(a,b)$

证明
$[{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同理$

5.2欧几里得算法

公式
$∀a,b∈N,b≠0,gcd(a,b)=gcd(b,amodb)\forall a,b \in \mathbb{N},b\neq 0,gcd(a,b) = gcd(b,a\mod b)$

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

$若a<b,那么amodb=a,gcd(b,amodb)=gcd(b,a)=gcd(a,b)若a<b,那么a\mod b = a,gcd(b,a\mod b) = gcd(b,a) = gcd(a,b)$
$gcd(b,a-b),因为a-b=a\mod b,gcd(a,b) = gcd(b,a\mod b)$

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

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

欧几里得算法实现

int gcd(int a,int b){//当b=0时，gcd(a,0)=aif(!b){return a;}else{return gcd(b,a%b);}
}

6. 欧拉函数

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

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

公式：
$依据算术基本定理，若N=p_1^{c_1}p_2^{c_2}…p_k^{c_k}，则$
$ϕ(N)=N∗p1−1p1∗p2−1p2∗…∗pk−1pk=N∗∏质数p∣N(1−1p)\phi(N) = 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})$

证明：
$用到了容斥原理，参考《算法进阶指南》上的证明，设 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互质的个数。$

代码如下：

int phi(int n){int ans = n;for(int i = 2; i <= n/i; i ++ ){if(n % i == 0){ans = ans/i*(i - 1);while(n % i == 0) n/=i;}}if(n > 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 euler(int n){//1的欧拉函数是1phi[1] = 1;for(int i = 2; i <= n; i ++ ) phi[i] = i;for(int i = 2; i <= n; i ++ ){//i是质数if(phi[i] == i){//对于j，多个i质因子for(int j = i; j <= n; j += i){phi[j] = phi[j]/i*(i - 1);}}}
}

线性筛法求欧拉函数
$若imodpj==0,ϕ(i∗pj)=ϕ(i)∗pj若i\mod pj == 0,\phi(i*pj) = \phi(i)*pj$
$否则，ϕ(i∗pj)=ϕ(i)∗pj∗(1−1pj)=ϕ(i)∗(pj−1)否则，\phi(i*pj) = \phi(i)*pj*(1-{1\over pj}) = \phi(i)*(pj – 1)$

int primes[N],cnt;//存储质数
int st[N];//st[i]:i的最小质因子
int phi[N];//phi[i]:表示i的欧拉函数void euler(int n){for(int i = 2; i <= n; i ++ ){if(!st[i]) st[i] = i,primes[++cnt] = i,phi[i] = i - 1;for(int j = 1; j <= cnt; j ++ ){if(primes[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]已经有这个质因子if(i % primes[j] == 0){phi[i*primes[j]] = phi[i] * primes[j];}else{//primes[j]是新成员phi[i*primes[j]] = phi[i] * (primes[j] - 1);}}}
}

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

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

文章目录

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中每个数的欧拉函数

UIKit 框架图- iOS开发需要不断的深入理解

USB鼠标失灵了怎么办

赞助商推荐

最新文章

消息称哪吒汽车裁员赔偿方案为 N+1，全公司 9 月工资只发一半

strchr函数在c++中可以用么(c++strlen函数用法)

android是什么意思(powerbyandroid是什么意思)

控制面板的作用是什么(控制面板的作用是什么它可以完成哪些工作至少举出四个)

python编译器安装教程(windows如何安装python)

大顶堆是升序还是降序(按大顶堆将序列调整为堆例子)

ip地址私有地址范围(ip地址设置为192.168.1.110)

过期域名抢注怎么办(域名过期多长时间可以抢注)

国外网站空间推荐(推荐几个国外的网站看文)

屏幕暗屏时间怎么调(屏幕暗屏是什么原因造成的)

标签

点击排行

英特尔确认未来数代处理器不会采用 Lunar Lake 同款 MoP 封装级内存方案

oppo问答系统技术路线

pikachu通关教程~~~~

怎么打印网页内容(如何打印网页选中的内容图片)

游戏装机新爆款出现!锐龙5 7600X3D配RTX 4060游戏性能如何?

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

文章目录

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中每个数的欧拉函数

UIKit 框架图- iOS开发需要不断的深入理解

USB鼠标失灵了怎么办

赞助商推荐

最新文章

消息称哪吒汽车裁员赔偿方案为 N+1，全公司 9 月工资只发一半

标签

点击排行

英特尔确认未来数代处理器不会采用 Lunar Lake 同款 MoP 封装级内存方案

oppo问答系统技术路线

pikachu通关教程~~~~

怎么打印网页内容(如何打印网页选中的内容图片)

游戏装机新爆款出现!锐龙5 7600X3D配RTX 4060游戏性能如何?

关注我们的公众号