质数筛选

1、埃式筛法：

1.1 思路

从2开始遍历所有数字，将没有标记的数字作为质数。同时在遍历的时候，如果该数字是质数，则需要将该质数的所有倍数进行标记。

1.2 代码

int get_prime(int x){
    int num=0;
    for(int i=2;i<=x;i++){
        if(!vist[i]){
            prime[num++]=i;
            for(int j=i+i;j<=x;j=j+i){
                vist[j]=true;
            }
        }
    }
    return num;
}

2、线性筛法：

2.1 思路

该算法与埃氏筛法不同，该算法在遍历时，不管该数字是否为质数，都需要进行标记操作。
具体为：每次遍历，都要将该数字与所得到的质数从小到大进行相乘，并将得到的结果标记。因为相乘的是质数，所以1~n每个数字最多只会被标记1次。且为了防止标记超过一次，所以要保证质数小于被遍历数字的最小质因子。

2.2 代码

int get_prime(int n){
    int num=0;
    for(int i=2;i<=n;i++){
        if(!vist[i])
            prime[num++]=i;
        for(int j=0;prime[j]<=n/i;j++){
            vist[prime[j]*i]=true;
            if(i%prime[j]==0)
                break;
        }
    }
    return num;
}