# Prime Sieve of Eratosthenes.cpp

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
}
}
}
```