#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
*/
