Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // C++ program to print all primes smaller than or equal to
- // n using Sieve of Eratosthenes
- // Time complexity O(n*log(log(n)))
- #include <bits/stdc++.h>
- using namespace std;
- void SieveOfEratosthenes(int n)
- {
- bool prime[n+1];
- memset(prime, true, sizeof(prime));
- for (int p=2; p*p<=n; p++)
- {
- // If prime[p] is not changed, then it is a prime
- if (prime[p] == true)
- {
- for (int i=p*p; i<=n; i += p)
- prime[i] = false;
- }
- }
- // Print all prime numbers
- for (int p=2; p<=n; p++)
- if (prime[p])
- cout << p << " ";
- }
- int main()
- {
- int n=0;
- cout<< "Enter your number"<< endl;
- cin>>n;
- cout << "Following are the prime numbers smaller "
- << " than or equal to " << n << endl;
- SieveOfEratosthenes(n);
- return 0;
- // Time complexity O(n*log(log(n)))
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement