---
tags: codebook
---

{%hackmd theme-dark %}

# sieve of eratosthenes

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

struct prime{
    unsigned long long range;
	vector<unsigned long long> v;
	decltype(v.cend()) end(){return v.cend();}
	decltype(v.cbegin()) begin(){return v.cbegin();}
	bool operator[](const unsigned long long& x){
		while(x>=range)
			init(range,range+(1<<16)),range+=(1<<16);
		return binary_search(v.begin(),v.end(),x);
	}
	void init(const unsigned long long& ori,const unsigned long long& x){
		vector<bool> b(x-ori,true);
		for(auto i=v.begin(),r=upper_bound(v.begin(),v.end(),sqrt(x));i!=r;i++)
			for(unsigned long long j=*i*(ori/(*i)+bool(ori%(*i)));j<x;j+=*i) 
				b[j-ori]=false;
		for(unsigned long long i=ori,j;i<x;i++)
			if(b[i-ori]) for(v.push_back(i),j=i+i;j<x;j+=i)
				b[j-ori]=false;

	}
	prime(const unsigned long long& x=2):range(x+1),v(1,2){init(3,x+1);}
};

## original_version

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
bool arr[20'000'000];
void eratosthenes() {
	memset(arr, 0, sizeof(arr));
	arr[0] = arr[1] = true;
	int sqrtn = sqrt(20000000);
	for (int i = 2; i <= sqrtn; i++)
		if (!arr[i])
			for (int k = (20000000 - 1) / i, j = i * k; k >= i; k--, j -= i)
				if (!arr[k])
					arr[j] = true;
}