// Program name:  Sieve

// Purpose:  To implement the sieve of Erasothenes to compute prime

// numbers between 2 and a number input by the user.



// Win32 console application



#pragma hdrstop



#include < iostream.h >

#include < fstream.h >

#include < math.h >

#include < assert.h >

#include < stdio.h >

#include < conio.h >



#define PRIME_FILE "primes.dat"

#define MAX 64000



void User_input(int &number);

void Find_primes(int number,bool primes[MAX]);

void Primes_to_file(int number,bool primes[MAX]);



void main()

{

	int number;

	bool primes[MAX];



	User_input(number);

	Find_primes(number,primes);

	Primes_to_file(number,primes);

	return;

}



void User_input(int &number)

{

	number = 1;

	while ((number < 2) || (number > MAX))

	{

		cout << "Find Prime Numbers" << endl << endl;

		cout << "Find the prime numbers between 2 and ... ";

		cin >> number;

		cout << endl;

		if ((number < 2) || (number > MAX))

		{

			cout << "The number must be between 2 and " << MAX;

			cout << "!" << endl << endl;

		}

	}

	return;

}



void Find_primes(int number,bool primes[MAX])

{

	int count,count1;



	for (count = 2;count <= number;count++)

		primes[count] = true;

	for (count = 2;count <= (int)(sqrt(number));count++)

	{

		for (count1 = count;count1 <= (number / count);count1++)

			primes[count * count1] = false;

	}

	count1 = 0;

	for (count = 2;count <= number;count++)

	{

		if (primes[count] == true)

			count1++;

	}

	cout << count1 << " prime number have been stored in the file.";

	cout << endl << endl;

	cout << "Press any key to continue ... " << endl;

	getche();

	return;

}



void Primes_to_file(int number,bool primes[MAX])

{

	ofstream prime_file;

	int count;



	prime_file.open(PRIME_FILE);

	remove(PRIME_FILE);

	prime_file.close();

	prime_file.open(PRIME_FILE);

	assert(!prime_file.fail());

	for (count = 2;count <= number;count++)

	{

		if (primes[count] == true)

			prime_file << count << " ";

	}

	prime_file.close();

	return;

}