エラトステネスの篩
(Math/Sieve.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Math/Sieve.hpp"

概要

エラトステネスの篩です

O(nloglogn)

Verified with

• test/yuki2855.test.cpp

Code

vector<bool> sieve(int n){
    vector<bool> ret(n+1,true);
    ret[0]=false;
    if(n>0) ret[1]=false;
    for(int i=2;i*i<=n;i++){
        if(!ret[i]) continue;
        for(int j=i*2;j<=n;j+=i) ret[j]=false;
    }
    return ret;
}

#line 1 "Math/Sieve.hpp"
vector<bool> sieve(int n){
    vector<bool> ret(n+1,true);
    ret[0]=false;
    if(n>0) ret[1]=false;
    for(int i=2;i*i<=n;i++){
        if(!ret[i]) continue;
        for(int j=i*2;j<=n;j+=i) ret[j]=false;
    }
    return ret;
}

Back to top page