写模板， 线性筛

筛质数：
1 需要：bitset位标记，vector存储质数
2 流程：标记了就是质数，加到vector。用当前数遍历所有已知质数进行标记，直到质数跑完或者质数为当前数的因子。
3 注意事项： 合数被标记的原理是因为每个合数都由最小质因子来标记，所以当质因子为i的因子时，直接break。
4 延申：根据线性筛可以找到每个数的第一个质因子。如果被标记了那这个质数就算它自己，否则就是标记它时使用的质因子。
5 线性筛欧拉函数： 初始化0和1要为1。如果i和prime不是因子关系，那么可以通过积性性质直接计算。因为欧拉函数是积性函数。如果i%prime==0，那么i * prime这个合数，它的质因子数量应该是i的互质数数量的prime倍，这个好理解。 如果i是prime，那么比他小的互质数数量就是i - 1.

//今天写完基础筛的基本框架，然后在这个质数的基础上延申功能。

bitset<100000010> bs;
vector<int> prime_values;
void sievePrimes(int x = static_cast<int> (1e7)){
	bs.set();
	bs[0] = bs[1] = 1;
	first_prime.resize(x + 1);
	for (int i = 2; i <= x; ++i){
		if (bs[i]){
			prime_values.emplace_back(i);
		}
		for (const auto& prime : prime_values){
			if (1ll * prime * prime > x){
				break;
			}
			bs[prime * i] = 0;
			if (i % prime == 0){
				break;
			}
		}
	}
}

vector<int> first_prime;
vector<int> prime_values;
void sieveFirstPrime(int x = int(1e7)){
	first_prime.assign(x + 1, -1);
	for (int i = 2; i <= x; ++i){
		if (first_prime[i] == -1){
			prime_values.emplace_back(i);
			first_prime[i] = i;
		}
		for (const auto& prime : prime_values){
			if (1ll * prime * prime > x){
				break;
			}
			first_prime[i * prime] = prime;
			if (i % prime == 0){
				break;
			}
		}
	}
}


vector<int> prime_values;
vector<int> euler_values;
bitset<100000100> bs;
void sieveEuler(int x = int(1e7)){
	bs.set();
	bs[0] = bs[1] = 0;
	euler_values.resize(x + 1);
	euler_values[0] = 1;
	euler_values[1] = 1;
	for (int i = 2; i <= x; ++i){
		if (bs[i]){
			prime_values.emplace_back(i);
			euler_values[i] = i - 1;
		}
		for (const auto& prime : prime_values){
			if (1ll * prime * i > x){
				break;
			}
			bs[i * prime] = 0;
			if (i % prime == 0){
				euler_values[i * prime] = euler_values[i] * prime;  //这里假设i = 4, prime = 2. 可知prime做的只是一个倍数的作用。
				break;
			}
			euler_values[i * prime] = euler_values[i] * euler_values[prime];
		}
	}
}