Codeforces-Codechef-Solutions/Prime_Generator.cpp at main · Rahulverma0711/Codeforces-Codechef-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
int N=100000;
int seive[1000000];
void createSeive()
{

    for(int i=2;i<=N;i++)
    seive[i]=1;

    for(int i=2;i<=N/i;i++)
    {
        if(seive[i]==1)
        {
            for(int j=i*i;j<=N;j=j+i)
            {
                seive[j]=0;
            }
        }
    }
}
void segmentedSeive()
{
    createSeive();
    int l,r;
    vector<int>prime;
    cin>>l>>r;
    for(int i=2;i*i<=r;i++)
    {
        if(seive[i]==1)
        prime.push_back(i);
    }
    int dummy[r-l+1];
   for(int i=0;i<r-l+1;i++)
   dummy[i]=1;
   for(auto pr:prime)
   {
       int firstmultiple=(l/pr)*pr;
       if(l%pr) firstmultiple+=pr;
       for(int j=max(firstmultiple,pr*pr);j<=r;j+=pr)
       {
           dummy[j-l]=0;
       }
   }

   for(int i=l;i<=r;i++)
   {
      if(i!=1){
       if(dummy[i-l]==1)
       cout<<i<<"\n";
      }

   }


}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
    segmentedSeive();
    cout<<"\n";
}
return 0;
}