Fast Prime Number Generator

[Lonesome Ducky]

Not totally irrlicht related, but may come in handy.
Calculates 1,000,000 prime numbers in roughly 2 seconds on my 2.3 ghz processor, while the next fastest method (that isn't a sieve) took 15. I know sieves are likely faster, but I tried to keep memory consumption relatively low. Code:

Code: Select all

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

std::vector<unsigned int> findPrimeFast(int count) {
	std::vector<unsigned int> primeList;
	unsigned int root = 1;
	primeList.push_back(2);
	unsigned int test = 1;
primetest:
	while (primeList.size() < count) {
		test += 2;
		while ((test/root)>root) root++;
		bool isPrime = true;
		for (int y = 0; y < primeList.size(); y++) {
			if (primeList[y] > root) {
				primeList.push_back(test);
				goto primetest;
			}
			if (test%primeList[y] == 0) {
				goto primetest;
			}
		}
		primeList.push_back(test);
	}
	return primeList;
}

And a test run against the fastest non-sieve I could find:

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <vector>
#include <math.h>
using namespace std;

void PrimeFunc(unsigned __int64* PrimeList){
    unsigned __int64 Prime = 1;
    unsigned __int64 Root = 1;
    unsigned __int64 PrimeCount = 0;

prime_start:
while(PrimeCount < 1000000){
    Prime += 2;
    while((Prime / Root) > Root) Root++;
    for(unsigned __int64 Test = 3;Test <= Root;Test+=2){
        if(Prime % Test == 0) goto prime_start;
        }
    PrimeList[PrimeCount] = Prime;
    PrimeCount++;
    }

return;
}

std::vector<unsigned int> findPrimeFast(int count) {
	std::vector<unsigned int> primeList;
	unsigned int root = 1;
	primeList.push_back(2);
	unsigned int test = 1;
primetest:
	while (primeList.size() < count) {
		test += 2;
		while ((test/root)>root) root++;
		bool isPrime = true;
		for (int y = 0; y < primeList.size(); y++) {
			if (primeList[y] > root) {
				primeList.push_back(test);
				goto primetest;
			}
			if (test%primeList[y] == 0) {
				goto primetest;
			}
		}
		primeList.push_back(test);
	}
	return primeList;
}


int main() {
	int start = GetTickCount();
	std::vector<unsigned int> cake2 = findPrimeFast(1000000);
	int end = GetTickCount();
	cout << "Time: " << end-start << "ms" << endl;
	start = GetTickCount();
	unsigned __int64 *ar = new unsigned __int64[1000000];
	PrimeFunc(ar);
	end = GetTickCount();
	cout << "Time: " << end-start << "ms" << endl;

	return 0;
}

Hopefully someone finds this useful

[Dareltibus]

ah i'm memory back to math course.


the prime func must create itself the array i think. it is safer. actually there is no input in the func about the 1000000 size. pretty nice. The memory usage is only the prime array good work.

Time needed in debug mode 22 seconds. (for PrimeFunc) (4Ghz)
(157 seconds for the slowest function between the two)

you can rewrite it using irrlicht types for using it in a game
i think this will be usefull if you "built-int" all prime numbers in a table in a source file making the executable 1-5 MB bigger but reducing to 0 (few clock cycles) computing time.

I'm not sure where to use a prime table in a game. Never thinked about that.


but it will be usefull to someone.