本题可以用两种筛法来解，分别是埃氏筛法和欧拉筛法。
埃氏筛法：
基本思想与原理：
初始化：创建一个从 222 到 nnn 的连续 bool 列表，初始标记所有数为 truetruetrue。
筛选过程：
从最小的素数 222 开始，筛去其所有倍数。
取下一个未被筛去的数（即下一个素数），重复筛去其倍数。
重复上述步骤，直到处理完所有小于等于根号n的数。
终止条件：当某素数的平方超过 n 时，剩余未标记的数均为素数。
优化：筛去某素数 ppp 的倍数时，可从 p的2次方p的2次方p的2次方开始筛（因更小的倍数已被更小的素数筛去）。
正确性证明：
关键点：每个合数必被其最小素因数筛去。
设 mmm 为合数，其最小素因数为 ppp，则 m=p×k(k≥p)m=p×k(k≥p)m=p×k(k≥p)。当算法处理 ppp 时，会筛去 ppp 的倍数（包括 mmm）。
若 mmm 未被筛去，则其最小素因数必大于当前处理的素数，这与算法步骤矛盾。
总结：所有合数均被筛去，剩余未标记的数为素数。
核心代码：
时间复杂度为 O(nloglogn)O(nloglogn)O(nloglogn)。
欧拉筛法：
基本思想与原理：
初始化：
创建一个 bool 类型的数组 is_prime[]，初始标记所有数为 true。
维护一个质数列表 Prime，用于动态存储已发现的素数。
筛选过程：
遍历每个整数 iii 从 222 到 nnn：
若 i 是素数，将其加入 Prime 列表。
对当前已知的所有素数 ppp
计算合数 m=i×pjm=i×pjm=i×pj 。
若 m>n，终止内层循环。
将 mmm 标记为合数。
关键步骤：若 iii 能被 pjpjpj 整除，终止内层循环。
正确性证明：
存在性：
设 mmm 是合数，其最小质因数为 pminpminpmin,则 m=pmin ×k。m=pmin ×k。m=pmin ×k。
当算法遍历到 kkk 时（此时 kkk 尚未被筛去），会计算 m=pmin×km=pmin×km=pmin×k 并标记成合数。
由于 pminpminpmin是 m 的最小质因数，pminpminpmin≤k，因此 kkk 会在遍历过程中被处理。
唯一性：
假设存在另一个素数 p′>pminp′>pminp′>pmin也能生成 m=p′×k′m=p′×k′m=p′×k′。
由于 pminpminpmin是 mmm 的最小质因数，必有 pmin∣k′pmin ∣k′pmin∣k′。
当算法遍历到 k′k′k′时，由于 pmin∣k′pmin∣k′pmin∣k′，内层循环会在处理 pminpminpmin后终止，不会用更大的 p′p′p′生成 mmm。
核心代码：
时间复杂度为 O(n)O(n)O(n)。
