## Example Generating Prime Numbers using Sieve of Eratosthenes Algorithm

Example of how to generate prime numbers using Sieve of Eratosthenes algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

primes.cpp:

#include<iostream>
#include<vector>
#include<stdio.h>
#include<ctime>
#include<math.h>
#include<string.h>
using namespace std;

//
// generatePrimesSlow()
// The array arr store the prime numbers up to and including x
// To test if a number i is prime, see if any prime number
// before i divides i evenly. If no prime number does, i is prime
// and is added to our array of prime numbers.
// Note: We should never see a number less than 2 in our array!
//
void generatePrimesSlow(int x, int * arr, int * amount)
{
int count = 0; // numbers currently in the array

for(int i=2; i<=x; i++) {
bool isPrime = true;
for (int j=0; j<count; j++) {
if (i % arr[j] == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
arr[count] = i;
count++;
}
}
*amount = count;
}

//
// generatePrimesFast()
// The array arr stores our prime numbers up to and including x
// To generate these numbers, we use the the Sieve of Eratosthenes
// Visit http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
// for the explanation of the algorithm.
//
void generatePrimesFast(int x, int * arr, int * amount)
{
int num = 2;
int count = 0;
bool *boolArr = new bool[x+1];
//bool boolArr[x];
memset(boolArr, true, (x+1)*sizeof(bool));
for(int i=2; i<=x; i++) {
if (boolArr[i]) {
arr[count] = i;
count++;
int temp = i+i;
while (temp <= x) {
boolArr[temp] = false;
temp += i;
}
}
}
*amount = count;
}

int main() {
cout << 'Up to what number would you like to generate primes? ';
int max;
cin >> max;
cout << endl;

// This will be our array to hold the prime numbers.
// Notice that this is probably way too much memory, since not every
// number up to max will be prime
// In fact, very very few numbers will be, let's try to free up some
// memory by using some math
// I think a bound for the number of primes up to N is N/lg(N)
// Let's try it

int amount = 0;
int num_primes;
if (max > 150) {
double x = max;
double actualNumberOfPrimes = x/(log(x)-4);
//double actualNumberOfPrimes = x/(log(x));
num_primes = (int) actualNumberOfPrimes;
}
else
num_primes = max;
int arr[num_primes+1];
memset(arr,0,sizeof(arr));
//generatePrimesFast(max, arr, &amount);
generatePrimesSlow(max, arr, &amount);

cout << 'Here are the prime numbers from 2 to ' << max << endl;
for (int i=0; i < amount; i++) {
cout << arr[i] << endl;
}
}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

## Code Examples in C++

Here are some code examples written in C++
Even do they are written in C++, I would advice to compile them in Linux as I did. If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks
NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. I do not take responsibilities of how they are used.