SHARE
TWEET

Untitled

a guest Dec 3rd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C++ program to print all primes smaller than or equal to
  2. // n using Sieve of Eratosthenes
  3.  
  4. // Time complexity O(n*log(log(n)))
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. void SieveOfEratosthenes(int n)
  10. {
  11.  
  12.     bool prime[n+1];
  13.     memset(prime, true, sizeof(prime));
  14.  
  15.     for (int p=2; p*p<=n; p++)
  16.     {
  17.         // If prime[p] is not changed, then it is a prime
  18.         if (prime[p] == true)
  19.         {
  20.  
  21.             for (int i=p*p; i<=n; i += p)
  22.                 prime[i] = false;
  23.         }
  24.     }
  25.     // Print all prime numbers
  26.     for (int p=2; p<=n; p++)
  27.        if (prime[p])
  28.           cout << p << " ";
  29. }
  30.  
  31. int main()
  32. {
  33.     int n=0;
  34.     cout<< "Enter your number"<< endl;
  35.     cin>>n;
  36.     cout << "Following are the prime numbers smaller "
  37.          << " than or equal to " << n << endl;
  38.     SieveOfEratosthenes(n);
  39.     return 0;
  40.  
  41.     // Time complexity O(n*log(log(n)))
  42. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top