素数列挙
(math/prime_list.hpp)

#pragma once
#include<vector>
#include<bitset>
#include<cmath>
#include<set>

/**
 * @brief 素数列挙
 */

std::bitset<500'000'001> p;
std::vector<long long> prime_list(int n) {
    p.set();
    p[0]=0;
    for(int i=2;i*i<=n;++i){
        if(!p[i])continue;
        for(int j=2*i;j<=n;j+=i)p[j]=0;
    }
    std::vector<long long>list;
    for(int i=2;i<=n;++i)if(p[i])list.push_back(i);
    return list;
}

#line 2 "math/prime_list.hpp"
#include<vector>
#include<bitset>
#include<cmath>
#include<set>

/**
 * @brief 素数列挙
 */

std::bitset<500'000'001> p;
std::vector<long long> prime_list(int n) {
    p.set();
    p[0]=0;
    for(int i=2;i*i<=n;++i){
        if(!p[i])continue;
        for(int j=2*i;j<=n;j+=i)p[j]=0;
    }
    std::vector<long long>list;
    for(int i=2;i<=n;++i)if(p[i])list.push_back(i);
    return list;
}