#define MAX 1000000
int st[MAX], pr[MAX], cnt;

int main() {
	int n;

	for (int i = 2; i <= n; i++) {
		if (!st[i]) pr[++cnt] = i;
		for (int j = 1; i % pr[j] && pr[j] <= n / i; j++)
			st[pr[j] * i] = 1;
			//pr[j]是i的最小质因子
	}

	return 0;
}