#includebits/stdc.h typedef long long ll; using namespace std; //埃氏筛求素数返回vectorll时间复杂度O(nloglogn) vectorll zhishushai(ll n){ vectorll primes; if(n2) return primes; vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; for (int i 2; i * i n;i){ //思想从 2 开始如果是 if(is_prime[i]){ //质数就把它所有倍数标记为合数。 for (int j i * i; j n;ji){//优化只需要筛到 到 sqrt(n) 的质数即可 is_prime[j] false; //因为大于 sqrt(n) 的质数的倍数在小于 sqrt(n) 的质数的倍数中已经被筛掉了。 } } } for (int i 2; i n;i){ if(is_prime[i]) primes.push_back(1LL*i); } return primes; } //欧拉筛线性筛求素数返回vectorll时间复杂度O(n) vectorll oulashai(int n){ vectorll primes; if(n2) return primes; vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] 0; for (int i 2; i n;i){//思想每个合数只被它的最小质因子筛掉一次因此复杂度是线性的。 if(is_prime[i]) //没有被筛掉的数就是质数 primes.push_back(1LL*i); for(int p:primes){ if(p*in) //如果p*in说明i的最小质因子已经大于sqrt(n)所以不需要再筛了 break; is_prime[p * i] false;//筛掉合数 if(i%p0) //如果i能被p整除说明p是i的最小质因子那么i的倍数中p*i已经被筛掉了所以不需要再筛了 break; } } return primes; } int main(){ int _ 1; cin _; //vectorll primeszhishushai(1000000); vectorll primesoulashai(1000000); while(_--){ int n; cin n; for (int i 0; i n; i){ cout1LL*primes[i]*primes[i1] ; } } return 0; }欧拉筛相比埃氏筛欧拉筛不会重复筛拥有同样两个因子的数egia*bb*a(aba,bsqrt(n)),埃氏筛先遍历到a时会让b*a再把结果i筛掉遍历到b时会让a*b再把结果i筛掉这样会重复筛掉同一个数所以引出了欧拉筛欧拉筛每个合数只会被它的最小质因子筛掉一次设合数 x它的最小质因子是 p。令 ix/p。(xp*i)因为 p 是 x 的最小质因子所以 i 的所有质因子都大于等于 p。在欧拉筛内层循环中当外层循环到 i 时会从小到大枚举质数 p′对于所有 p′p因为 p′ 小于 p而 i 的所有质因子都 ≥p所以 p′ 不可能整除 i即i % p ! 0不会 break当枚举到 p 时标记i * p x此时如果i%p0就 break不再继续枚举更大的质数。这样就保证了 x 只会被 i 和它的最小质因子 p 标记一次。而如果 x被其他质因子qp 标记那么对应的 i′x/q 一定含有质因子 p。当外层循环到 i′时内层会先枚举到 p此时i % p 0会直接 break根本轮不到 q 去标记 x。所以 x 不会被重复标记。题目链接Dashboard - Codeforces Round 1090 (Div. 4) - Codeforces