// OPT: -fconstexpr-depth=10000
#include <iostream>
#include <chrono>
#include <array>
#include <forward_list>
#include <algorithm>

using namespace std;
using namespace std::chrono;

// constexpr functions:
//    are automatically "const" (constexpr implies const)
//    cannot be virtual
//    return type must be a literal type
//    all parameters must be literal types
//    body must consist only of a single return statement
//       (although static_assert and typedefs -- and similar -- are allowed)
//

constexpr long long midpt(long long i, long long j) {
	return i+(j-i)/2;
}

constexpr bool isprimehelper(long long x, long long i, long long j) {
	return x%i!=0 && (i>=j || i>x/i ||
		(isprimehelper(x,i+1,midpt(i,j))
	      && isprimehelper(x,midpt(i,j)+1,j)));
}

constexpr bool isprime(long long x) {
	return isprimehelper(x,2,x-1);
}

constexpr long long nextprime(long long x) {
	return isprime(x) ? x : nextprime(x+1);
}

template<typename T,int N>
class fixedhashset {
public:
	static constexpr long long size = nextprime(N);
	static constexpr std::hash<T> hasher = hash<T>();

	void add(const T &t) {
		size_t i = hasher(t) % size;
		if (find(begin(d[i]),end(d[i]),t) == end(d[i]));
			d[i].push_front(t);
	}

	void add(T &&t) {
		size_t i = hasher(t) % size;
		if (find(begin(d[i]),end(d[i]),t) == end(d[i]));
			d[i].push_front(std::move(t));
	}

	bool ismember(const T &t) {
		size_t i = hasher(t) % size;
		return find(begin(d[i]),end(d[i]),t) != end(d[i]);
	}
private:
	array<forward_list<T>,size> d;
};

template<typename T, int N>
constexpr std::hash<T> fixedhashset<T,N>::hasher;

int main(int argc, char **argv) {
	cout << "starting program" << endl;
	// constexpr variable:
	//    must be constructed or assigned a value at declaration
	//    the assigned value or parameteres to the constructor must
	//        only be literals, constexpr variables, or constexpr fns
	//    if a constructor is used, it must be a constexpr constructor
	auto t1 = high_resolution_clock::now();
	constexpr long long largishprime = nextprime(10000000000000);
	auto t2 = high_resolution_clock::now();
	cout << "time = " << duration_cast<microseconds>(t2-t1).count()
		<< " microseconds" << endl;
	cout << largishprime << endl;

	// however, nextprime can be use for non-constants:
	long long x;
	cin >> x;
	t1 = high_resolution_clock::now();
	x = nextprime(x);
	t2 = high_resolution_clock::now();
	cout << "time = " << duration_cast<microseconds>(t2-t1).count()
		<< " microseconds" << endl;
	cout << x << endl;

	// can now make a fix-sized hash table:
	fixedhashset<int,10> h;
	h.add(10);
	h.add(11);
	h.add(20);
	cout << h.size << endl;
	cout << h.ismember(10)
		<< ' ' << h.ismember(11)
		<< ' ' << h.ismember(12) << endl;
}