质数

质数

质数的定义

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

质数的判断

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

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

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

质数筛法

现在我们要求111到nnn中全部质数.

暴力

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

埃氏筛法

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

欧拉线性筛法

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

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)O(n)

质因数分解

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

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

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

欧拉函数

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

性质

  1. 对于质数nnn,φ(n)=n1φ(n)=n-1φ(n)=n−1.
  2. 对于质数ppp,φ(pk)=(p1)pk1φ(p^k)=(p-1)*p^{k-1}φ(pk)=(p−1)∗pk−1.
  3. 对于互质的n,mn,mn,m,φ(n)φ(m)=φ(nm)φ(n)*φ(m)=φ(n*m)φ(n)∗φ(m)=φ(n∗m).
  4. 对于奇数nnn,φ(2n)=φ(n)φ(2*n)=φ(n)φ(2∗n)=φ(n).
  5. 对于n(n>1)n(n>1)n(n>1),k=1nk(gcd(n,k)=1)=φ(n)n/2\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=0k\%p=0k%p=0,φ(kp)=φ(k)pφ(k*p)=φ(k)*pφ(k∗p)=φ(k)∗p.
  7. k%p!=0k\%p!=0k%p!=0,φ(kp)=φ(k)(p1)φ(k*p)=φ(k)*(p-1)φ(k∗p)=φ(k)∗(p−1).
  8. 对于互质的a,ma,ma,m,aφ(p)1(modp)a^{φ(p)} \equiv 1 \pmod {p}aφ(p)≡1(modp).
  9. knnφ(k)=n\sum_{k\mid n}^n{φ(k)}=n∑k∣nn​φ(k)=n
  10. φ(n)=knnφ(k)nkφ(n)=\sum_{k\mid n}^n{φ(k)*\frac{n}{k}}φ(n)=∑k∣nn​φ(k)∗kn​.

计算公式及证明

nnn的质因数分解为p1c1p2c2p_1^{c_1}*p_2^{c_2}*p1c1​​∗p2c2​​∗…pici*p_i^{c_i}∗pici​​.
φ(n)=np11p1p21p2φ(n)=n*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*φ(n)=n∗p1​p1​−1​∗p2​p2​−1​∗…pi1pi*\frac{p_i-1}{p_i}∗pi​pi​−1​
证明:设p,qp,qp,q是nnn的质因子.
111-nnn中,ppp的倍数有np\frac{n}{p}pn​个,qqq的倍数有nq\frac{n}{q}qn​个,pqp*qp∗q的倍数有np+q\frac{n}{p+q}p+qn​个.
所以111到n1n-1n−1中与p,qp,qp,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;

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

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 私信 关注
上一篇:shell编程题(七)


下一篇:洛谷P1049装箱问题(01背包)