C/C++ - scomposizione numeri primi

Io un programma simile non l'ho mai fatto... mi sarebbe piaciuto vedere come e' stato risolto.

vabbè se deve venire piero a chiedermelo

#include <iostream>
#include <windows.h>
#include <math.h>

#include <vector>
#include <fstream>

using namespace std;

bool bDone = false;
DWORD dwTime;
ULONG n;
ULONG ulMax;

// Delay between updates
const int DELAY = 1000;

// Async procedure to show progress
DWORD WINAPI ThreadProc(LPVOID lpParameter) {

	DWORD dwTempTime;
	ULONG ulNumber;
	ULONG ulLastNumber = 3;

	HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);

	COORD cCoord;

	cCoord.X = 0;
	cCoord.Y = 20;

	do {

		
		dwTempTime = GetTickCount() - dwTime;
		ulNumber = n;

		ULONG ulDiff = ulNumber - ulLastNumber;

		float fPerc = ((float)ulNumber / ulMax) * 100;

		SetConsoleCursorPosition(hOut, cCoord);

		cout << "Time : " << dwTempTime << " ms" << endl;
		cout << "Number: " << ulNumber << "/" << ulMax << " (" << fPerc << "%)" << endl;
		cout << "Speed: " << (float)ulDiff / DELAY << " numbers/msec" << endl << endl;

		ulLastNumber = ulNumber;

		Sleep(DELAY);

	} while(!bDone);


	return 0;


}

int main(int argc, char *argv[]) {


	cout << " *** PrimeFinder by HeDo ***" << endl << endl;

	cout << "Max prime number: ";
	cin >> ulMax;

	// Vector containing the prime numbers found
	vector<ULONG> lstPrime;

#ifdef _EDEBUG

	cout << endl;

	cout << "Capacity: " << lstPrime.capacity() << endl;

	cout << endl << " -> After reserve() " << endl << endl;

#endif

	// Let's reserve enough space
	lstPrime.reserve(ulMax);

#ifdef _EDEBUG

	lstNoise.reserve(ulMax);

	cout << "Capacity: " << lstPrime.capacity() << endl;

#endif

	cout << endl;
		
	// The 2 and 3 are added this way coz of optimization
	lstPrime.push_back(2);
	lstPrime.push_back(3);

	DWORD dwID;

	// Create and start the monitor thread
	HANDLE hTh = CreateThread(NULL, 0, ThreadProc, NULL, 0, &dwID);

	// Let's measure the time
	dwTime = GetTickCount();

	bool bPrime;

	// We can skip the even number
	for (n = 3; n < ulMax; n += 2) {
				

#ifdef _EDEBUG

		cout << "Checking number " << n << endl;

#endif

		bPrime = true;

		// This method is called "factorization test", it's the slowest but the simpliest to implement :)
		for (ULONG h = 0; h < lstPrime.size(); h++) {
					

#ifdef _EDEBUG
			cout << "Selected " << lstPrime[h] << endl;
#endif

			// We dont need to test prims above the square root of the number
			if (lstPrime[h] > sqrt((double)n)) {

#ifdef _EDEBUG
				cout << "Breaking: " << lstPrime[h] << " is higher than n / 3 = " << n / 3 << endl;
#endif

				break;

			}

#ifdef _EDEBUG
			cout << "Real prime check: " << n << " % " << lstPrime[h] << " = " << n % lstPrime[h] << endl;
#endif

			// Remainder check
			if (n % lstPrime[h] == 0) {

#ifdef _EDEBUG
				cout << " -> Not prime number " << endl;
#endif

				bPrime = false;

				break;

			}


		}

		// If it is prime
		if (bPrime) {

#ifdef _EDEBUG

			cout << " !> " << n << " is prime" << endl;
#endif
			// Add it to our vector
			lstPrime.push_back(n);

		}

	}

	// How long did it take?
	dwTime = GetTickCount() - dwTime;

	bDone = true;

	// "out.txt" contains the prime numbers found
	ofstream out("out.txt", ios::out);

	// "noise.csv" contains the deltas between the primes
	ofstream noise("noise.csv", ios::out);

	out << lstPrime[0] << ", ";

	// Write the files
	for(int n = 1; n < lstPrime.size(); n++) {

		out << lstPrime[n] << ", ";

		noise << (lstPrime[n] - lstPrime[n - 1]) << "; ";

	}

	out.close();
	noise.close();

	// Performance check
	cout << endl << "Time: " << dwTime << "ms, for " << lstPrime.size() << " numbers";

	cout << endl << endl;

	system("PAUSE");

	return 0;
}

/*

x86

 *** PrimeFinder by HeDo ***

Max prime number: 1000000

Time: 8844ms, for 78498 numbers

x64

 *** PrimeFinder by HeDo ***

Max prime number: 1000000

Time: 9078ms, for 78498 numbers

intel x86

 *** PrimeFinder by HeDo ***

Max prime number: 1000000

Time: 8829ms, for 78498 numbers

intel x86

 *** PrimeFinder by HeDo ***

Max prime number: 1000000


Time: 8843ms, for 78498 numbers

*/