src/math/eratosthenes.hpp

View this file on GitHub
Last update: 2026-01-30 22:16:29+09:00
Include: #include "src/math/eratosthenes.hpp"

Depends on

src/template.hpp

Code

#include "../template.hpp"

vector<int> eratosthenes(int N){
    vector<int> is(N+2,1);
    is[0]=is[1]=0;
    for(long i=2;i*i<=N;++i){
        if(is[i]){
            for(int j=i*i;j<=N;j+=i) is[j]=0;
        }
    }
    return is;
}

struct SegmentSieve {
    long L,R;
    vector<int> P;
    SegmentSieve (long _L,long _R):L(_L),R(_R){
        int sq=sqrtl(R)+1;
        vector<int> sm(sq,1);
        P.assign(R-L+1,1);
        for(long i=2;i * i<=R;i++){
            if(!sm[i]) continue;
            for(long j=i*i;j<R;j+=i) sm[j]=0;
            long start=max((L+i-1)/i,i*2);
            for(long j=start;j<R;j+=i) P[j-L]=0;
        }
    }
    bool operator[](long k) const {return P[k-L];}
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/math/eratosthenes.hpp"

vector<int> eratosthenes(int N){
    vector<int> is(N+2,1);
    is[0]=is[1]=0;
    for(long i=2;i*i<=N;++i){
        if(is[i]){
            for(int j=i*i;j<=N;j+=i) is[j]=0;
        }
    }
    return is;
}

struct SegmentSieve {
    long L,R;
    vector<int> P;
    SegmentSieve (long _L,long _R):L(_L),R(_R){
        int sq=sqrtl(R)+1;
        vector<int> sm(sq,1);
        P.assign(R-L+1,1);
        for(long i=2;i * i<=R;i++){
            if(!sm[i]) continue;
            for(long j=i*i;j<R;j+=i) sm[j]=0;
            long start=max((L+i-1)/i,i*2);
            for(long j=start;j<R;j+=i) P[j-L]=0;
        }
    }
    bool operator[](long k) const {return P[k-L];}
};