sieve of Eratosthenes Algorithm
The Sieve of Eratosthenes is an efficient and ancient algorithm used for finding all prime numbers up to a specified integer. It was invented by the Greek mathematician Eratosthenes in the 3rd century BCE and is still one of the most popular methods for finding prime numbers today. The algorithm works by iteratively marking the multiples of each prime number, starting with the smallest prime (2), and then moving on to the next unmarked number. As it progresses, it effectively eliminates all non-prime numbers, leaving behind only the prime numbers within the specified range.
The algorithm begins by creating a list of numbers from 2 to the maximum number you want to search for primes (let's call it 'n'). Initially, all the numbers in the list are unmarked. Starting with the first number (2), the algorithm marks it as prime and proceeds to mark all its multiples (excluding itself) as non-prime. Then, it moves on to the next unmarked number (which is 3 in this case), marks it as prime, and marks all its multiples as non-prime. This process continues iteratively until all the numbers in the list have been visited. By the end of the algorithm, all the unmarked numbers remaining in the list are prime numbers, and the marked numbers are their multiples. This method is particularly efficient because it avoids redundant calculations and only processes the multiples of actual prime numbers, allowing it to quickly generate a list of prime numbers up to 'n'.
/*
* Sieve of Eratosthenes is an algorithm to find the primes
* that is between 2 to N (as defined in main).
*
* Time Complexity : O(N)
* Space Complexity : O(N)
*/
#include <iostream>
using namespace std;
#define MAX 10000000
int primes[MAX];
/*
* This is the function that finds the primes and eliminates
* the multiples.
*/
void sieve(int N)
{
primes[0] = 1;
primes[1] = 1;
for (int i = 2; i <= N; i++)
{
if (primes[i] == 1)
continue;
for (int j = i + i; j <= N; j += i)
primes[j] = 1;
}
}
/*
* This function prints out the primes to STDOUT
*/
void print(int N)
{
for (int i = 0; i <= N; i++)
if (primes[i] == 0)
cout << i << ' ';
cout << '\n';
}
/*
* NOTE: This function is important for the
* initialization of the array.
*/
void init()
{
for (int i = 0; i < MAX; i++)
primes[i] = 0;
}
int main()
{
int N = 100;
init();
sieve(N);
print(N);
}
