素数筛法(埃氏筛法、线性筛法)

素数筛法:用于筛选出素数
核心思想:用一个数筛选其余的数

普通筛法:
时间复杂度为O(nlogn)

#include <iostream>
#define N 100
bool vis[N] = { false };// 0到N-1的元素都没有被标记
int primes[N]; // 存放素数
int tot; 


//普通筛法
int main() {
    vis[0] = vis[1] = true; // 0和1不是素数

    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            primes[++tot] = i; // 找到一个素数，存放到primes中
        }
        for (int j = 2 * i; j < N; j += i) {
            vis[j] = true; // 将i的倍数都标记为已被筛掉
        }
    }

    for (int i = 1; i < tot; i++) {
        std::cout << primes[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

继续优化的话可以 只用质数去筛 ，这也就是埃氏筛法:
时间复杂度为:O(nloglogn)

int main() {
    vis[0] = vis[1] = true; // 0和1不是素数
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            primes[++tot] = i; // 找到一个素数，存放到primes中
            for (int j = i * i; j < N; j += i) {
                vis[j] = true; // 将i的倍数都标记为已被筛掉
            }
        }
    }

    for (int i = 1; i < tot; i++) {
        std::cout << primes[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

继续优化
线性筛 :
每个数都被其最小的质因数筛掉
时间复杂度为O(n)

int main() {
    vis[0] = vis[1] = true;
    for (int i = 2; i <= N; i++) {
        if (!vis[i]) {
            primes[++tot] = i;
        }
        for (int j = 1; i * primes[j] < N; j++) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }

    for (int i = 1; i < tot; i++) {
        std::cout << primes[i]<< " ";
    }
    std::cout << std::endl;

    return 0;
}