前言

之前写的埃式筛法复杂度达 $O (n * l o g n * l o g n)$ ，在大数字的时候可能复杂度还不够理想。这种做法对于一个合数有可能会筛了多次，导致重复做功。引入欧拉筛法能够解决这种多次筛同一个数字的情况，理论算法复杂度 $O (n)$ 。精髓在于 $p v a l [j] ∣ i$ 时就结束本次筛选。

Code：

const int maxn = (int)1e7+5;

bool vis[maxn];
int pval[maxn],len;

void prime () {
	memset(vis, true, sizeof(vis));
	memset(pval, -1, sizeof(pval));
	vis[0] = vis[1] = false;
	int i, j, k;
	len = 0;
	for (i = 2; i < maxn; i++) {
		if (vis[i]) pval[++len] = i;
		for (j = 1; j <= len; j++) {
			k = pval[j] * i;
			if (k >= maxn) break;
			vis[k] = false;
			if (i % pval[j] == 0) break;
		}
	}
}