Prime Sieve of Eratosthenes.cpp

From Algorithmist
Jump to navigation Jump to search

This is an implementation of [[{{{name}}}]] in [[{{{lang}}}]].

This version of the sieve stores all the numbers of sieve. But uses slightly more memory as opposed to a bit array of size n.

#include <cmath>
#include <vector>

/*primes is a list of primes, n is all the primes you want to generate.. from 2 to n*/
void genPrimes(std::vector<int>& primes, int n)
{
	for (int i = 2; i <= n; i++)
	{
		int root = int(sqrt(i)) + 1;    /*remember the square root*/
		bool found = false;       /*prime found?*/

		for (std::vector<int>::const_iterator it = primes.begin(); it != primes.end() && *it < root; it++)
		{
			if (i % *it == 0)
			{
				found = true;
				break;
			} /*this is not prime*/
		}

		if (!found)
		{
			primes.push_back(i); /*this is a prime*/
		}
	}
}

There is a faster way to get primes using a bitset and taking only odd numbers in the sieve.

#include <iostream>
#include <bitset>

#define SIZE 10000000
#define MAX (int)(SIZE - 3) / 2

using namespace std;

int primes[MAX + 1];                                                   //array that stores the primes up to sqrt(SIZE)
bitset<MAX + 1> bset;                                                  //auxiliary bitset used to make the sieve

void setPrimes()
{
	int i, j;

	for (i = 0; (i * i) <= SIZE; i++)                                          //we only have to get primes up to sqrt(SIZE)
	{
		if (!bset.test(i))
		{
			for (j = i + 1; (2 * j + 1)*(2 * i + 3) <= SIZE; j++)
			{
				bset.set(((2 * j + 1)*(2 * i + 3) - 3) / 2);                   //setting all non-primes
			}
		}
	}

	primes[0] = 2;                                                     //store the first prime (that is 2)

	for (i = 1, j = 0; j < MAX + 1; j++)
	{
		if (!bset.test(j))
		{
			primes[i++] = 2 * j + 3;                                        //store the remaining odd primes
		}
	}
}