M5 - 欧拉筛-质数筛

bool ar[maxn >> 1u];
vector< int > prs;

int euler(const int n) {
	prs.reserve(n / log(n) * 1.2);
	if (n < 2) return 0;
	for (int i = 3; i <= n; i += 2) {
		if (!ar[i >> 1u]) prs.push_back(i);
		for (int j = 0, des = n / i; prs[j] <= des; j++) {
			ar[prs[j] * i >> 1u] = true;
			if (i % prs[j] == 0) break;
		}
	}
	return prs.size() + 1;
}