題目如下：

區間[a,b)指的是所有滿足a≤x<b的整數(根據背景也可能是實數)所構成的集合。
其中，b以內的合數的最小質因數一定不超過。如果有以內的素數表的話,就可以把埃氏篩法運用在[a,b)上了。就是說,先分別做好[2,√b)的表和[a,b的表,然后從[2,√b)的表中篩得素數的同時,也將其倍數從[a,b)的表中劃去,最后剩下的就是區間[a,b)內的素數了。
超詳解代碼：

#include<iostream> #include<algorithm> #define maxn 9999999 using namespace std; typedef long long ll;//對長整型起別名 bool is_prime_small[maxn]; bool is_prime[maxn]; ll a, b;//定義全局變量 //對區間[a,）內的整數執行篩法。is_prime[i-a]=true->i是素數 void solve(ll a, ll b) {for (ll i = 0; (ll)i * i < b; i++)is_prime_small[i] = true;//對0到根號b進行初始化for (ll i = 0; i < b - a; i++)is_prime[i] = true;//將[a,b)問題轉化為[0,b-a)for (ll i = 2; (ll)i * i < b; i++){if (is_prime_small[i]){for (ll j = 2 * i; (ll)j * j < b; j += i)is_prime_small[i] = false;for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i)is_prime[j - a] = false;//max(2LL,(a+i-1)/i)*i是求距離a最近，但比a大的數//2LL是2的長整型}} } //將[a,b)問題轉化為[0,b-a)，is_prime[i]->true,其為素數 int fun() {int res = 0;for (ll i = 0; i < b - a; i++)if (is_prime[i])res++;return res; } int main() {while (cin >> a >> b){solve(a, b);int res;res = fun();cout << res << endl;}return 0; }

總結

以上是生活随笔為你收集整理的区间筛法超详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。