- 质数的个数是无限的。
-
试除法：若一个正整数 \(N\) 为合数，则存在一个能整除 \(N\) 的数 \(T\) ，其中 \(2 \le T \le \sqrt{N}\) 。
- 时间复杂度为 \(O(\sqrt{N})\) 。
- 代码实现
bool isprime(int n) { if (n < 2) return false; for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; } -
筛法
- Eratosthenes 筛法（埃式筛法）
- 时间复杂度 \(O(N \times \log \log N)\)
- luogu P3912 素数个数
#include<bits/stdc++.h> using namespace std; bool m[100000010]; int main() { int n,i,j,ans=0; cin>>n; m[1]=1; for(i=2;i<=sqrt(n);i++) { if(m[i]==0) { for(j=2;i*j<=n;j++) { m[i*j]=1; } } } for(i=2;i<=n;i++) { if(m[i]==0) { ans++; } } cout<<ans; return 0; }
- 线性筛法（欧拉筛法）
- 时间复杂度 \(O(N)\)
- luogu P3383 【模板】线性筛素数
#include<bits/stdc++.h> using namespace std; #define ll long long #define sort stable_sort #define endl '\n' int prime[100000001],sum[10],len=0; bool vis[100000001]; void isprime(int n) { int i,j; memset(vis,false,sizeof(vis)); for(i=2;i<=n;i++) { if(vis[i]==false) { len++; prime[len]=i; } for(j=1;j<=len&&i*prime[j]<=n;j++) { vis[i*prime[j]]=true; if(i%prime[j]==0) { break; } } } } int main() { int n,q,i,k; cin>>n>>q; isprime(n); for(i=1;i<=q;i++) { cin>>k; cout<<prime[k]<<endl; } return 0; }
- Eratosthenes 筛法（埃式筛法）
-
算术基本定理（唯一分解定理）
- 任何一个大于 \(1\) 的正整数都能唯一分解成有限个的质数的乘积，可写作 \(N=p_1^{c_1}p_2^{c_2}……p_m^{c_m}\) ，其中 \(c_i\) 都是正整数， \(p_i\) 都是质数，且满足 \(p_1<p_2<……<p_m\) 。
-
互质
- 若 \(\forall a,b \in \mathbb{N},\gcd(a,b)=1\) ，则称 \(a,b\) 同余。
- 对于三个数或更多个数的情况，将 \(\gcd(a,b,c)=1\) 的情况称为 \(a,b,c\) 互质；将 \(\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1\) 的情况称为 \(a,b,c\) 两两互质。
-
欧拉函数
- \(1 \sim N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记作 \(\varphi(N)\) 。
- 依据算术基本定理，有 \(N=p_1^{c_1}p_2^{c_2}……p_m^{c_m}\) ，则 \(\varphi(N)=N \times \dfrac{p_1-1}{p_1} \times \dfrac{p_2-1}{p_2} \times ... \times \dfrac{p_m-1}{p_m}=N \times \prod\limits_{i=1}^{m}{(1- \dfrac{1}{p_i})}\) ，其中 \(c_i\) 都是正整数， \(p_i\) 都是质数，且满足 \(p_1<p_2<……<p_m\) 。
- 证明：设 \(p,q(p \ne q)\) 是 \(N\) 的质因子， \(1 \sim N\) 中 \(p\) 的倍数共有 \(\left\lfloor\dfrac{N}{p}\right\rfloor\) 个， \(q\) 的倍数共有 \(\left\lfloor\dfrac{N}{q}\right\rfloor\) 个，依据容斥原理， \(1 \sim N\) 中不与 \(N\) 含有共同质因子 \(p\) 或 \(q\) 的个数为 \(N -\left\lfloor\dfrac{N}{p}\right\rfloor-\left\lfloor\dfrac{N}{q}\right\rfloor+\left\lfloor\dfrac{N}{p \times q}\right\rfloor=\left\lfloor N \times (1- \dfrac{1}{p}- \dfrac{1}{q}+ \dfrac{1}{p \times q})\right\rfloor=\left\lfloor N \times (1- \dfrac{1}{p}) \times (1- \dfrac{1}{q})\right\rfloor\) 。类似地，可在 \(N\) 的全部质因子上使用容斥原理，即可得到与 \(N\) 互质的数的个数。
- 性质
- \(\varphi(1)=1\) 。
- 若 \(p\) 为质数，则 \(\varphi(p)=p-1,\varphi(p^k)=p^k-p^{k-1}=(p-1) \times p^{k-1}\) 。
- 证明：设 \(n=p^k\) ，比 \(n\) 小的正整数有 \(p^k-1\) 个。其中共有 \(p^{k-1}-1\) 个数能被 \(p\) 整除，即这些数不与 \(p^k\) 互质。故 \(\varphi(p^k)=p^k-1-(p^{k-1}-1)=p^k-p^{k-1}=(p-1) \times p^{k-1}\) 。
- 对于两个不同的质数 \(p,q\) ，有 \(n=p\times q\) ，则 \(\varphi(n)=(p-1)(q-1)\) 。
- 若 \(\forall n>1\) ，则 \(1 \sim n\) 中与 \(n\) 互质的数的和为 \(\dfrac{n \times \varphi(n)}{2}\) 。
- 证明：依据更相减损法，有 \(\gcd(n,x)=\gcd(n,n-x)\) ，即与 \(n\) 互质的数 \(x,n-x\) 成对出现，平均值为 \(\dfrac{n}{2}\) 。
- 若 \(n\) 为奇数，则 \(\varphi(2n)=\varphi(2) \times \varphi(n)=\varphi(n)\) 。
- 若 \(2<n\) ，则 \(2|\varphi(n)\) 。
- 若 \(a,b\) 互质，则 \(\varphi(ab)=\varphi(a) \times \varphi(b)\) 。
- 证明：依据算术基本定理，设 \(a=\prod\limits_{i=1}^n p_i^{c_i},b=\prod\limits_{i=1}^m q_i^{c'_i}\) ，又因为 \(a,b\) 互质，所以不存在一组 \(i,j\) 满足 \(p_i=q_j\) ，故 \(\varphi(ab)=ab \times \prod\limits_{i=1}^n (1-\dfrac{1}{p_i}) \times \prod\limits_{i=1}^m (1-\dfrac{1}{q_i})\) ，又有 \(\varphi(a)=a \times \prod\limits_{i=1}^n (1-\dfrac{1}{p_i}),\varphi(b)=b \times \prod\limits_{i=1}^m (1-\dfrac{1}{1_i})\) ，故 \(\varphi(ab)=\varphi(a) \times \varphi(b)\) 。
- 由本条性质可知 \(\varphi\) 是积性函数。
- 若 \(a|b\) ，则 \(\varphi(ab)=a \times \varphi(b)\) 。
- 证明：因为 \(ab\) 和 \(b\) 所有的质因子是相同的，只是部分质因子的指数发生变化，故 \(\varphi(ab)=a \times \varphi(b)\) 。
- 若 \(a|b\) ，则 \(\varphi(a) | \varphi(b)\) 。
- 若 \(p\) 为质数，且 \(p|n,p^2|n\) ，则 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times p\) 。
- 证明：因为 \(p|n,p^2|n\) ，所以 \(n,\dfrac{n}{p}\) 有相同的质因子（其中 \(p\) 的指数不同），依据欧拉函数的计算公式，此时有 \(\dfrac{\varphi(n)}{\varphi(\dfrac{n}{p})}=p\) ，故 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times p\) 。
- 若 \(p\) 为质数，且 \(p|n,p^2 \nmid n\) ，则 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times (p-1)\) 。
- 证明：因为 \(p|n,p^2|n\) ，所以 \(n,\dfrac{n}{p}\) 互质，又因为 \(\varphi\) 是积性函数，故 \(\varphi(n)=\varphi(\dfrac{n}{p}) \times \varphi(p)=\varphi(\dfrac{n}{p}) \times (p-1)\) 。
- \(n=\sum\limits_{d|n}^{}\varphi(d)\) 。
- 证明：设 \(k\) 满足 \(k<n,\gcd(k,n)=d\) ，则 \(\gcd(\dfrac{k}{d},\dfrac{n}{d})=1\) ；设 \(f(x)\) 表示满足 \(\gcd(k,n)=x\) 的 \(k\) 的个数，则 \(n=\sum\limits_{i=1}^n f(i)\) 。又因为 \(\dfrac{k}{x}\) 与 \(\dfrac{n}{x}\) 互质，有 \(f(x)=\varphi(\dfrac{n}{x})\) ，则 \(n=\sum\limits_{i|n}^{}\varphi(\dfrac{n}{i})\) 。易知 \(i\) 与 \(\dfrac{n}{i}\) 是一一对应的，故 \(n=\sum\limits_{d|n}^{}\varphi(d)\) 。
- 依据算术基本定理，有 \(n=\prod\limits_{i=1}^m p_i^{c_i}\) ，又因为 \(\varphi\) 是积性函数，则 \(\varphi(n)=\prod\limits_{i=1}^m \varphi(p_i^{c_i})=\prod\limits_{i=1}^m (p_i-1) \times p_i^{{c_i}-1}=\prod\limits_{i=1}^m (1-\dfrac{1}{p_i}) \times p_i^{c_i}=n \times \prod\limits_{i=1}^m (1-\dfrac{1}{p_i})=n \times \prod\limits_{i=1}^m \dfrac{p_i-1}{p_i}\) 。
- PS：无意义（用计算式证定义，又用定义证计算式）。
- 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \gcd(i,n)=\sum\limits_{d|n}^{} d \times \varphi({\dfrac{n}{d}})\) 。
-
证明：
\(\begin{aligned}\sum\limits_{i=1}^{n} \gcd(i,n) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d|n}^{} d \times \sum\limits_{i=1}^{n} [\gcd(i,n)=d] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d|n}^{} d \times \sum\limits_{i=1}^{\dfrac{n}{d}} [\gcd(i,\dfrac{n}{d})=1] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d|n}^{} d \times \varphi({\dfrac{n}{d}})\end{aligned}\)
- 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j)=\sum\limits_{d=1}^{n} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor^2\) 。
-
证明：
\(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d| \gcd(i,j)}^{} \varphi(d) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|i,d|j}^{} \varphi(d) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n} \varphi(d) \sum\limits_{i=1}^{n} [d|i] \sum\limits_{j=1}^{n} [d|j] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n} \varphi(d) \left\lfloor\dfrac{n}{d}\right\rfloor \left\lfloor\dfrac{n}{d}\right\rfloor \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor^2 \end{aligned}\)
-
拓展：若 \(n,m\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j)=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor \times \left\lfloor\dfrac{m}{d}\right\rfloor\) 。
-
证明：
\(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \gcd(i,j) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d| \gcd(i,j)}^{} \varphi(d) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d|i,d|j}^{} \varphi(d) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \sum\limits_{i=1}^{n} [d|i] \sum\limits_{j=1}^{m} [d|j] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \left\lfloor\dfrac{n}{d}\right\rfloor \left\lfloor\dfrac{n}{d}\right\rfloor \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{\min(n,m)} \varphi(d) \times \left\lfloor\dfrac{n}{d}\right\rfloor \times \left\lfloor\dfrac{m}{d}\right\rfloor\end{aligned}\)
-
- 若 \(n\) 为正整数，则 \(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j)= \sum\limits_{d=1}^{n}d \times \;(\;2 \times \;(\;\sum\limits_{i=1}^{\dfrac{n}{d}}\varphi(i)\;)\;-1)\) 。
-
证明：
\(\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i,j) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d=1}^{n}d \times [\gcd(i,j)=d] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d=1}^{n}d \times [\gcd(\dfrac{i}{d},\dfrac{j}{d})=1] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \sum\limits_{i=1}^{\dfrac{n}{d}} \sum\limits_{j=1}^{\dfrac{n}{d}} [\gcd(i,j)=1] \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \;(\sum\limits_{i=1}^{\dfrac{n}{d}} \times \;(2\;(\sum\limits_{j=1}^{i} [\gcd(i,j)=1])\;)\;-1) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \;(\;(\;\sum\limits_{i=1}^{\dfrac{n}{d}} \times 2\varphi(i)\;)\;-1) \end{aligned}\)
\(\begin{aligned}&=\sum\limits_{d=1}^{n}d \times \;(\;2 \times \;(\;\sum\limits_{i=1}^{\dfrac{n}{d}}\varphi(i)\;)\;-1) \end{aligned}\)
-
拓展：若 \(n,m\) 为正整数，则有link(太长就放这里了)。
- 例题
- SP4141 ETF - Euler Totient Function | UVA10179 Irreducable Basic Fractions | UVA10299 Relatives
- 对原数进行分解质因数，顺便求出欧拉函数。
int phi(int n) { int ans=n,i; for(i=2;i<=sqrt(n);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; } - UVA11327 Enumerating Rational Numbers
- 线性筛欧拉函数（时间复杂度为 \(O(N)\) ）板子
void euler(ll n) { memset(vis,false,sizeof(vis)); phi[1]=1; for(ll i=2;i<=n;i++) { if(vis[i]==false) { len++; prime[len]=i; phi[i]=i-1;//phi[i]表示i的欧拉函数 } for(ll j=1;j<=len&&i*prime[j]<=n;j++) { vis[i*prime[j]]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else { phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } }
- SP4141 ETF - Euler Totient Function | UVA10179 Irreducable Basic Fractions | UVA10299 Relatives
-
积性函数
- 若 \(a,b\) 互质，有 \(f(ab)=f(a) \times f(b)\) ，那么称函数 \(f\) 为积性函数。
- 性质
- 若函数 \(f\) 是积性函数，依据算术基本定理，有 \(n=\prod\limits_{i=1}^m p_i^{c_i}\) ，则 \(f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})\) 。
-