素数问题

1、试除法判断素数

时间复杂度：O(√n)

bool is_prime(int n)
{
    if(n<=1) return false;
    for(int i=2;i*i<=n;++i){//比i<=sqrt(n)好,小心i*i溢出
       if(n%i==0) return false;
    }
    return true;
}

2、埃氏筛（Eratosthenes)

时间复杂度：O(nloglogn)

void getPrime(int n)
{
    memset(vis,true,sizeof(vis));
    vis[0]=vis[1]=false;
    for(int i=2;i*i<=n;++i){//小心i*i溢出
       if(vis[i]){
         for(int j=i*i;j<=n;j+=i)//for(int j=i;j*i<=n;++j)
            vis[j]=false;//           vis[i*j]=false;
       }
    }
}

3、线性筛/欧拉筛（Euler）

时间复杂度：O(n)

void getPrime()
{
    //memset(vis,false,sizeof(vis));
    //memset(primes,0,sizeof(primes));
    int cnt=0;
    for(int i=2;i<=n;++i){
       if(!vis[i]) primes[++cnt]=i;//i是素数
       for(int j=1;j<=cnt&&primes[j]<=n/i;++j){
          vis[primes[j]*i]=true;//true：非素数
          if(i%primes[j]==0) break;
       }
    }
}

4、素数拆分（质因数分解）

Function 1:

时间复杂度：O(√n)

void Fac(int n)
{
    int m=0;
    for(int i=2;i<=sqrt(n);++i){
       if(n%i==0){
         p[++m]=i,c[m]=0;
         while(n%i==0) n/=i,c[m]++;
       }
    }
    if(n>1) p[++m]=n,c[m]=1;
}

Function 2:

时间复杂度：O(√s)
s为√n内质数个数.

struct factor{
    int prime,cnt;
    factor(int p,int c):prime(p),cnt(c){}
};

void Fac(int n,vector <factor>&ans){
    ans.clear();
    if(n==1) return;
    for(int i=1;i<=m;++i){//m:素数个数
       if(n%primes[i]==0){
         factor f(primes[i],0);
         while(n%primes[i]==0) n/=primes[i],f.cnt++;
         ans.push_back(f);
       }
       if(n==1) return;
    }
    ans.push_back(factor(n,1));
}