【模板】素数筛

关于素数筛的介绍，可以浏览这篇文章：素数筛 - 五葉魔法书 (grimoire.cn)，本文给出一种更简洁的埃氏筛写法

/*
 * @Author: NorthCity1984
 * @LastEditTime: 2023-03-30 20:25:41
 * @Description:
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCity1984 All rights reserved.
 */
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

const int N = 1e6 + 10;
const int M = 1e9 + 10;
const int INF = INT32_MAX;

// 用于判断小于 size 的数字是否是素数
vector<bool> getPrimeMap(int size) {
    vector<bool> vis(size, true);
    for (int i = 2; i < size; i++) {
        if (!vis[i]) {
            continue;
        }
        for (int j = 2; j * i < size; j++) {
            vis[i * j] = false;
        }
    }
    return vis;
}

// 返回小于 size 的所有素数
vector<int> getPrimeList(int size) {
    vector<int> prime;
    vector<bool> vis(size, true);
    for (int i = 2; i < size; i++) {
        if (!vis[i]) {
            continue;
        }
        prime.push_back(i);
        for (int j = 2; j * i < size; j++) {
            vis[i * j] = false;
        }
    }
    return prime;
}

int main() {
    auto prime = getPrimeList(100);

    for (auto i : prime) {
        cout << i << " ";
    }
    cout << endl;

    auto primeMap = getPrimeMap(100);
    cout << "2 is " << (primeMap[2] ? "" : "not ") << "prime number" << endl;
    cout << "6 is " << (primeMap[6] ? "" : "not ") << "prime number" << endl;

    return 0;
}