质数(学习笔记)

质数的定理

1既不是质数,也不是合数;2是最小的质数,且是唯一的偶质数;

质数的个数是无限的;

任何一个大于1的正整数都能唯一分解为有限个质数的乘积;

(怎么感觉是小学数学背概念啊)

质数的判定（时间复杂度\(O(\sqrt{n})\)）

(直接贴代码吧)

bool is_prime(int n){
    for(int i=2;i*i<=n;i++)
      if(n%i==0) return false;
    return true;
}

质数的筛选

给定一个整数N,求出1~N之间的所有质数,称为质数的筛选问题.

Eratosthenes筛选法(时间复杂度O(N))

基本思想:质数的倍数一定不是质数;

void primes(int n){
    memset(v,0,sizeof(v)); //先假设全都是质数
    for(int i=2;i<=n;i++){
        if(v[i]) continue; //如果v[i]=1,i是合数
        cout<<i<<endl;
        for(int j=i;j<=n/i;j++) v[i*j]=1;
    }
}

线性筛法(一定掌握这个)

基本思想:我们在生成一个需要标记的合数时,每次向现有的数乘上一个质因子,并且让它是这个合数的最小质因子.

v数组记录每个数的最小质因子;

int v[N],prime[N];
void primes(int n){
    memset(v,0,sizeof(v));
    int m=0;           //统计质数数量
    for(int i=2;i<=n;i++){
        if(v[i]==0){   //i是质数
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(prime[j]>v[i]||prime[j]>n/i) 
                break;
          //i有比prime[j]更小的质因子,或者超出n的范围
            v[i*prime[j]]=prime[j];
          //prime[j]是合数i*prime[j]的最小质因子
        }
    }
    for(int i=1;i<=m;i++)
      cout<<prime[i]<<endl;
}

质因数分解

任何一个大于1的正整数都能唯一分解为有限个质数的乘积.

一个数N至多有一个大于\(\sqrt{n}\)的质因子.

void divide(int n){
    int m=0;//m记录正整数n的质因数的个数
    for(int i=2;i*i<=n;i++){
        if(n%i==0){    //i是质数
            p[++m]=i;  //p[]数组记录质因数
            c[m]=0;    //c[]数组记录质因数的幂
            while(n%i==0){
                n=n/i;
                c[m]++;
            }
        }
    }
    if(n>1){ //最后如果n不等于1,它一定是个质数
        p[++m]=n;
        c[m]=1;
    }
    for(int i=1;i<=m;i++)
      cout<<p[i]<<‘^‘<<c[i]<<endl;
}

质数(学习笔记)

原文：https://www.cnblogs.com/PPXppx/p/10332537.html