This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#include "Math/Sieve.hpp"
エラトステネスの篩です
O(nloglogn)
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; }