thehitmanranjan

Sieve Of Eratosthenes

Oct 4th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. int main() {
  5.     void sieve(int);
  6.     int n,t;
  7.     cin>>t;
  8.     while(t--)
  9.     {
  10.         cin>>n;
  11.         sieve(n);
  12.     }
  13.     return 0;
  14. }
  15. void sieve(int n)
  16. {
  17.     bool arr[n+1];
  18.     int j;
  19.     memset(arr,true,sizeof(arr));
  20.     for(int i=2;i*i<=n;i++)
  21.     {
  22.         if(arr[i]==true)
  23.         {
  24.             for(j=i*2;j<=n;j+=i)
  25.             {
  26.                 arr[j]=false;
  27.             }
  28.         }
  29.     }
  30.     for(int k=2;k<=n;k++)
  31.     {
  32.         if(arr[k]==true)
  33.         cout<<k<<" ";
  34.     }
  35.     cout<<endl;
  36. }
Add Comment
Please, Sign In to add comment