线性筛素数

使用欧拉筛法可以接近线性的时间内筛出一定范围内所有素数。

基本思想:如果$$a$$是素数,那么$$a*1,a*2,a*3,a*4,a*5…..$$都不是素数，这样就可以对一定范围内的非素数进行标记。

代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = long long int;
const int_t MAX = 10000;
char isPrime[MAX + 1];
vector primeTable;

int main() {
    //初始时，假设所有数都是素数
    memset(isPrime, 1, sizeof (isPrime));
    int_t n;
    cin>>n;
    //1当然不是素数
    isPrime[1] = 0;
    //i只需要枚举到sqrt(n),因为i>sqrt(n)的情况已经被考虑过了
    for (int_t i = 2; i <= sqrt(n + 0.5); i++) {
        //当外层循环执行到i时,如果i仍未被标记非素数，就说明i真的是素数
        //如果i不是素数,那样就不需要继续标记i*2,i*3,i*4....了 因为这些情况已经被标记了
        if (isPrime[i]) {
            for (int_t j = i * i; j <= n; j =j+i) {
                isPrime[j] = false;
            }
        }
    }
    for (int_t i = 1; i <= n; i++) {
        if (isPrime[i]) {
            primeTable.push_back(i);
        }
    }
    for (int_t prime : primeTable) {
        cout << prime << endl;
    }

    return 0;
}