sieve of erathso code example
Example 1: sieve of eratosthenes c++
#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] == true)
{
for (int i=p*p; i<=n; i += p)
prime[i] = false;
}
}
for (int p=2; p<=n; p++)
if (prime[p])
cout << p << " ";
}
int main()
{
int n = 30;
cout << "Following are the prime numbers smaller "
<< " than or equal to " << n << endl;
SieveOfEratosthenes(n);
return 0;
}
Example 2: sieve of eratosthenes pseudocode
find primes up to N
For all numbers a : from 2 to sqrt(n)
IF a is unmarked THEN
a is prime
For all multiples of a (a < n)
mark multiples of as composite
All unmarked nummbers are prime!