企业官网建设流程全解析

#include<bits/stdc++.h> typedef long long ll; using namespace std; //埃氏筛，求素数，返回vector<ll>，时间复杂度O(nloglogn) vector<ll> zhishushai(ll n){ vector<ll> primes; if(n<2) return primes; vector<bool> 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;j+=i){//优化：只需要筛到 到 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; } //欧拉筛（线性筛），求素数，返回vector<ll>，时间复杂度O(n) vector<ll> oulashai(int n){ vector<ll> primes; if(n<2) return primes; vector<bool> 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*i>n) //如果p*i>n，说明i的最小质因子已经大于sqrt(n)，所以不需要再筛了 break; is_prime[p * i] = false;//筛掉合数 if(i%p==0) //如果i能被p整除，说明p是i的最小质因子，那么i的倍数中，p*i已经被筛掉了，所以不需要再筛了 break; } } return primes; } int main(){ int _ = 1; cin >> _; //vector<ll> primes=zhishushai(1000000); vector<ll> primes=oulashai(1000000); while(_--){ int n; cin >> n; for (int i = 0; i < n; i++){ cout<<1LL*primes[i]*primes[i+1]<<" "; } } return 0; }

欧拉筛相比埃氏筛：

欧拉筛不会重复筛拥有同样两个因子的数，（eg：i=a*b=b*a，(a<b&&a,b<sqrt(n)),埃氏筛先遍历到a时，会让b*a，再把结果i筛掉，遍历到b时，会让a*b，再把结果i筛掉，这样会重复筛掉同一个数，所以引出了欧拉筛）

欧拉筛：每个合数只会被它的最小质因子筛掉一次

设合数 x，它的最小质因子是 p。
令 i=x/p。(x=p*i)

因为 p 是 x 的最小质因子，所以 i 的所有质因子都大于等于 p。

在欧拉筛内层循环中，当外层循环到 i 时，会从小到大枚举质数 p′：

• 对于所有 p′<p，因为 p′ 小于 p，而 i 的所有质因子都 ≥p，所以 p′ 不可能整除 i，即i % p' != 0，不会 break；

• 当枚举到 p 时，标记i * p = x；

• 此时如果i%p==0，就 break，不再继续枚举更大的质数。

这样就保证了 x 只会被 i 和它的最小质因子 p 标记一次。

而如果 x被其他质因子q>p 标记，那么对应的 i′=x/q 一定含有质因子 p。当外层循环到 i′时，内层会先枚举到 p，此时i' % p == 0，会直接 break，根本轮不到 q 去标记 x。所以 x 不会被重复标记。

题目链接：

Dashboard - Codeforces Round 1090 (Div. 4) - Codeforces