本题可以用两种筛法来解，分别是埃氏筛法和欧拉筛法。

埃氏筛法：

基本思想与原理：
初始化：创建一个从 $2$ 到 $n$ 的连续 bool 列表，初始标记所有数为 $true$。
筛选过程：
从最小的素数 $2$ 开始，筛去其所有倍数。
取下一个未被筛去的数（即下一个素数），重复筛去其倍数。
重复上述步骤，直到处理完所有小于等于根号n的数。
终止条件：当某素数的平方超过 n 时，剩余未标记的数均为素数。
优化：筛去某素数 $p$ 的倍数时，可从 $p的2次方$开始筛（因更小的倍数已被更小的素数筛去）。

正确性证明：

关键点：每个合数必被其最小素因数筛去。
设 $m$ 为合数，其最小素因数为 $p$，则 $m=p×k(k≥p)$。当算法处理 $p$ 时，会筛去 $p$ 的倍数（包括 $m$）。
若 $m$ 未被筛去，则其最小素因数必大于当前处理的素数，这与算法步骤矛盾。
总结：所有合数均被筛去，剩余未标记的数为素数。

核心代码：

void ai(int n){
	memset(is_p,true,sizeof(is_p));
	is_p[0] = is_p[1]=0;
    for(int i = 2;i * i <= n;i++){
    	if(is_p[i]){
    		for(int j  = i * i;j <= n;j += i){
				is_p[j] = false;
			}
		}
	}
}

时间复杂度为 $O(nloglogn)$。

欧拉筛法：
基本思想与原理：
初始化：
创建一个 bool 类型的数组 is_prime[]，初始标记所有数为 true。
维护一个质数列表 Prime，用于动态存储已发现的素数。
筛选过程：
遍历每个整数 $i$ 从 $2$ 到 $n$：

若 i 是素数，将其加入 Prime 列表。
对当前已知的所有素数 $p$
计算合数 $m=i×pj$ 。
若 m>n，终止内层循环。
将 $m$ 标记为合数。
关键步骤：若 $i$ 能被 $pj$ 整除，终止内层循环。
正确性证明：
存在性：
设 $m$ 是合数，其最小质因数为 $pmin$,则 $m=pmin​×k。$
当算法遍历到 $k$ 时（此时 $k$ 尚未被筛去），会计算 $m=pmin×k$ 并标记成合数。
由于 $pmin$是 m 的最小质因数，$pmin$≤k，因此 $k$ 会在遍历过程中被处理。
唯一性：
假设存在另一个素数 $p′>pmin$也能生成 $m=p′×k′$。
由于 $pmin$是 $m$ 的最小质因数，必有 $pmin ∣k′$。
当算法遍历到 $k′$时，由于 $pmin∣k′$，内层循环会在处理 $pmin$后终止，不会用更大的 $p′$生成 $m$。

核心代码：

void euler(int n){
	memset(is_p,1,sizeof(is_p));
	is_p[0] = is_p[1] = 0;
	for(int i = 2;i <= n;i++){
		if(is_p[i])prime[++cnt]=i;
		for(int j = 1;j <= cnt && (long long)i * prime[j] <= n;j++){
			is_p[i*prime[j]] = 0;
			if(i%prime[j] == 0)break;
		}
	}
}

时间复杂度为 $O(n)$。