programming-problem/spoj/prime genarator.cpp at master · skMomin/programming-problem · 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
#include<bits/stdc++.h>

using namespace std;
#define pb push_back
bool Check[1000000002];
int main()
{
   long long int n,m,t,p,q;
    scanf("%lld",&t);
    while(t--)
    {
         scanf("%lld%lld",&n,&m);
         for(int i=2;i<=sqrt(m)+1;i+=2)
        Check[i]=true;
        vector<long long int>prime;
    Check[2]=false;
    Check[1]=true;
    prime.pb(2);

    for(long long int i=3;i<=sqrt(m)+1;i+=2)
    {
        if(Check[i]==false)
        {
           //prime.pb(i);
             // cout<<i<<endl;

            for(long long int j=i*i;j<=m;j+=i)
            {

                Check[j]=true;
            }
        }
    }
    //prime.pb(10000000);
  //for(size_t t=0;t<prime.size();t++)
    //  cout<<prime[t]<<' ';

          // for(long long  j=n;j<=m;j++)
          // {

             //  Check[j]=true;

           //}
   //  }
       for(p=n;p<=m;p++)
        if(Check[p]==false)
        cout<<p<<endl;
         cout<<endl;
         prime.clear();
    }


    return 0;
}