区间筛素数

/* *********************************************** ┆ ┏┓　　　┏┓ ┆ ┆┏┛┻━━━┛┻┓ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　━　　　┃ ┆ ┆┃　┳┛　┗┳　┃ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　┻　　　┃ ┆ ┆┗━┓　马　┏━┛ ┆ ┆　　┃　勒　┃　　┆　　　　　　 ┆　　┃　戈　┗━━━┓ ┆ ┆　　┃　壁　　　　　┣┓┆ ┆　　┃　的草泥马　　┏┛┆ ┆　　┗┓┓┏━┳┓┏┛ ┆ ┆　　　┃┫┫　┃┫┫ ┆ ┆　　　┗┻┛　┗┻┛ ┆ ************************************************ */ #include <iostream> #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <algorithm> #include <functional> #define PI acos(-1) #define eps 1e-8 #define inf 0x3f3f3f3f #define debug(x) cout<<"---"<<x<<"---"<<endl typedef long long ll; using namespace std; const int NP = 100005; int ispri[NP] = {}, prime[NP], pcnt = 0; void getprime() { ispri[0] = ispri[1] = 1; for (long long i = 2; i < NP; i++) if (ispri[i] == 0) { prime[++pcnt] = i; for (long long j = i * i; j < NP; j += i) { ispri[j] = 1; } } } const int NI = 1000005; int iispri[NI], iprime[NI], icnt; void igetprime(int l, int r) { memset(iispri, 0, sizeof(iispri)); if (l < 2) { l = 2; } for (int i = 1; i <= pcnt && (long long)prime[i]*prime[i] <= r; i++) { int s = l / prime[i] + (l % prime[i] > 0); if (s == 1) { s = 2; } for (long long j = s; j * prime[i] <= r; j++) if (j * prime[i] >= l) { iispri[j * prime[i] - l] = 1; } } icnt = 0; for (int i = 0; i <= r - l; i++) if (!iispri[i]) { iprime[++icnt] = i + l; } } int main() { getprime(); int l, r; while (cin >> l >> r) { igetprime(l, r); for (int i = 1; i <= icnt; i++) { cout << iprime[i] << endl; } } return 0; } /************************************************ ┆ ┏┓　　　┏┓ ┆ ┆┏┛┻━━━┛┻┓ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　━　　　┃ ┆ ┆┃　┳┛　┗┳　┃ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　┻　　　┃ ┆ ┆┗━┓　 　┏━┛ ┆ ┆　　┃　 　┃　　┆　　　　　　 ┆　　┃　 　┗━━━┓ ┆ ┆　　┃　 AC代马 　　┣┓┆ ┆　　┃　 　　┏┛┆ ┆　　┗┓┓┏━┳┓┏┛ ┆ ┆　　　┃┫┫　┃┫┫ ┆ ┆　　　┗┻┛　┗┻┛ ┆ ************************************************ */