质数

• 质数的定义
• 质数的判断
• 质数筛法
• 暴力
• 埃氏筛法
• 欧拉线性筛法
• 质因数分解
• 欧拉函数
• 性质
• 计算公式及证明
• 算法实现

质数的定义

质数又称作素数.
质数是除了1和本身没有其他因数的数.
与之相反的是合数.
1不属于质数或合数.

质数的判断

假设我们要判断$n$n是不是质数.
从2枚举$n-1$n−1,若能整除$n$n,$n$n就不是质数.
时间复杂度$O(n)$O(n).
但因数是成对的(除了$\sqrt n$n​)
令$n=c_1 c_2$n=c1​c2​,假设$c_1 \le c_2$c1​≤c2​
则$c_1 \le \sqrt n , c_2 \ge \sqrt n$c1​≤n​,c2​≥n​
所以只需枚举到$\sqrt n$n​.

bool isprime(long long x) {
    for(int i=2; i<=sqrt(x); i++) {
        if(x%i==0) return false;
    }
    return true;
}

时间复杂度$O(\sqrt n)$O(n​).

质数筛法

现在我们要求$1$1到$n$n中全部质数.

暴力

最简单的办法就是判断每个数是否为质数.
时间复杂度$O(n \sqrt n)$O(nn​).

埃氏筛法

从$1$1到$\sqrt n$n​,若这个数没有被标记,即为质数.
只要发现了一个质数$t$t,就把从$1$1到$n$n中全部$t$t的倍数标记.
时间复杂度$O(n \log n)$O(nlogn)

欧拉线性筛法

对于每个$i(1<i<n)$i(1<i<n),筛去所有小于$i$i的质数与$i$i的乘积.
不难发现,有些合数被重复筛去.
设所有小于$i$i的质数分别为$p_1,p_2,...,p_j$p1​,p2​,...,pj​.
当$i\%p_k=0$i%pk​=0时,停止筛$i$i的倍数,即可避免重复.
因为当$l>k$l>k时,所有$i*p_l$i∗pl​都会被比$i$i大的数与$p_k$pk​的乘积筛去.

for(int i=2;i<=n;i++){
    if(!vis[i]) {
        cnt++;
        pri[cnt]=i;
    }
    for(int j=1;i*pri[j]<=n;j++){
        vis[i*pri[j]]=true;
        if(i%pri[j]==0) break;
    }
}

时间复杂度$O(n)$O(n)

质因数分解

一个数的质因数必定小于等于$\sqrt n$n​.
只需把$i$i从$2$2枚举到$\sqrt n$n​,从$n$n中去掉所有$i$i并做记录,就能求出$n$n的质因数.

for(int i=2;i<=sqrt(n);i++) {
    while(n%i==0) {
        n/=i;
        cnt[i]++;
    }
}

时间复杂度$O(\sqrt n)$O(n​)

欧拉函数

欧拉函数是从$1$1到$n-1$n−1的数中与$n$n互质的数的个数.
$φ(1)=φ(2)=1$φ(1)=φ(2)=1.

性质

1. 对于质数$n$n,$φ(n)=n-1$φ(n)=n−1.
2. 对于质数$p$p,$φ(p^k)=(p-1)*p^{k-1}$φ(pk)=(p−1)∗pk−1.
3. 对于互质的$n,m$n,m,$φ(n)*φ(m)=φ(n*m)$φ(n)∗φ(m)=φ(n∗m).
4. 对于奇数$n$n,$φ(2*n)=φ(n)$φ(2∗n)=φ(n).
5. 对于$n(n>1)$n(n>1),$\sum_{k=1}^n{k(gcd(n,k)=1)}=φ(n)*n/2$∑k=1n​k(gcd(n,k)=1)=φ(n)∗n/2.
6. 若$k\%p=0$k%p=0,$φ(k*p)=φ(k)*p$φ(k∗p)=φ(k)∗p.
7. 若$k\%p!=0$k%p!=0,$φ(k*p)=φ(k)*(p-1)$φ(k∗p)=φ(k)∗(p−1).
8. 对于互质的$a,m$a,m,$a^{φ(p)} \equiv 1 \pmod {p}$aφ(p)≡1(modp).
9. $\sum_{k\mid n}^n{φ(k)}=n$∑k∣nn​φ(k)=n
10. $φ(n)=\sum_{k\mid n}^n{φ(k)*\frac{n}{k}}$φ(n)=∑k∣nn​φ(k)∗kn​.

计算公式及证明

设$n$n的质因数分解为$p_1^{c_1}*p_2^{c_2}*$p1c1​​∗p2c2​​∗…$*p_i^{c_i}$∗pici​​.
则$φ(n)=n*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*$φ(n)=n∗p1​p1​−1​∗p2​p2​−1​∗…$*\frac{p_i-1}{p_i}$∗pi​pi​−1​
证明:设$p,q$p,q是$n$n的质因子.
则$1$1-$n$n中,$p$p的倍数有$\frac{n}{p}$pn​个,$q$q的倍数有$\frac{n}{q}$qn​个,$p*q$p∗q的倍数有$\frac{n}{p+q}$p+qn​个.
所以$1$1到$n-1$n−1中与$p,q$p,q互质的数的个数为
KaTeX parse error: No such environment: align* at position 7: \begin{̲a̲l̲i̲g̲n̲*̲}̲ n-\frac{n}{p}-…
其他质因子同理.

算法实现

对于求单个欧拉函数,分解质因数即可.

for(long long i=2;i<=sqrt(num);i++) {
    bool div=false;
    while(num%i==0) {
        div=true;
        num/=i;
    }
    if(div) ans=ans*(i-1)/i;
}
if(num>1) ans=ans*(num-1)/num;

时间复杂度与质因数分解一样.
但如果要求从$1$1到$n$n的数的欧拉函数,就可以通过打表法来求解.

for(int i=2;i<=MAXN;i++) {
    if(!phi[i]) {
        for(int j=i;j<=MAXN;j+=i) {
            if(!phi[j]) phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}

或是在欧拉筛时同时求出欧拉函数.

for(int i=2;i<=n;i++){
    if(!vis[i]) {
        cnt++;
        pri[cnt]=i;
        phi[cnt]=i-1;
    }
    for(int j=1;i*pri[j]<=n;j++){
        vis[i*pri[j]]=true;
        if(i%pri[j]==0) {
            phi[i*pri[j]]=phi[i]*pri[j];
            break;
        }
        phi[i*pri[j]]=phi[i]*(pri[j]-1);
    }
}

• 点赞
• 收藏
• 分享
• • 文章举报

gzezFISHER 发布了1 篇原创文章 · 获赞 0 · 访问量 6 私信 关注