质数

N足够大时，质数大约有N/InN个

质数的判定：

试除法——扫描2~sqrt(n)

质数的筛选：

Eratosthenes筛法基本思想——x的倍数都不是质数

1 for(int i=2;i<=n;i++){
2 
3     if(vis[i]) continue;
4 
5     vis[i]=1;cout<<i<<endl;
6 
7     for(int j=i;j<=n/i;j++) vis[i*j]=1;
8 
9 }//注意j是从i开始，因为小于x方的x的倍数已被标记了

线性筛基本思想——用vis数组来维护每个数的最小质因子

 1 for(int i=2;i<=n;i++){
 2 
 3     if(vis[i]==0){
 4 
 5         prime[++m]=i;
 6     
 7         vis[i]=i;//质数的最小质因子为本身
 8 
 9     }
10 
11     for(int j=1;j<=m;j++){//用比自己小的质因子来筛后面的数
12 
13         if(prime[j]>vis[i]||(prime[j]*i)>n) break;//前一个是i为合数的情况
14 
15         vis[prime[j]*i]=prime[j];
16 
17     }
18 
19 }

质因数的分解

试除法

for(int i=2;i<=n;i++){

    if(vis[i]==0){

        prime[++m]=i;

        vis[i]=i;//质数的最小质因子为本身

    }

    for(int j=1;j<=m;j++){//用比自己小的质因子来筛后面的数

        if(prime[j]>vis[i]||(prime[j]*i)>n) break;//前一个是i为合数的情况

            vis[prime[j]*i]=prime[j];

        }

}