Thread: cout == slow (prime numbers)

To heat511,

Do you mind to share your source code with the public so that a newbee like me could learn something?


Thanks.

I wrote a quick 'n' dirty prime finder for fun. There are probably lots of optimisations I've missed, but it can find 10,000 primes starting from zero in 30 seconds.

That is on my crappy PIII 800.

Code:

void FindPrimes(unsigned long HowMany, unsigned long StartNum)
{
	unsigned long *NumberArray;
	LARGE_INTEGER PerfFreq, CurrentCount, ElapsedCount, LaterCount;
	int ArrayCounter, Counter;
	int Minutes, Seconds;
	int DivBy;
	int DivNum;
	bool Timed = false;

	NumberArray = new unsigned long[50000];

	if(!StartNum)
		StartNum = 1;

	if(!QueryPerformanceFrequency(&PerfFreq))
	{
		cout << "No Performance counter installed, operation will not be timed.";
	}
	else
	{
		Timed = true;
		QueryPerformanceCounter(&CurrentCount);
	}

	cout << "Working..." << endl;

	ArrayCounter=0;

	for(Counter=0 ; Counter<HowMany ; Counter++)
	{
		if(ArrayCounter == 50000)
		{
			SaveArray(NumberArray, ArrayCounter);
			ArrayCounter=0;
		}
		
		if(!(StartNum%2))
		{
			StartNum++;
			Counter--;
			continue;
		}

		DivBy = 0;

		for(DivNum=1 ; DivNum!=StartNum ; DivNum++)
			if(!(StartNum % DivNum))
			{
				DivBy++;
				if(DivBy > 2)
				{
					StartNum++;
					Counter--;
					break;
				}
			}

		if(DivBy <= 2)
		{
			NumberArray[ArrayCounter] = StartNum;
			StartNum++;
			ArrayCounter++;
		}
	}

	SaveArray(NumberArray, ArrayCounter);

	if(Timed)
	{
		QueryPerformanceCounter(&LaterCount);
		ElapsedCount.QuadPart = LaterCount.QuadPart - CurrentCount.QuadPart;
		Seconds = ElapsedCount.QuadPart / PerfFreq.QuadPart; 

		if(Seconds > 60)
		{
			Minutes = Seconds/60;
			for(int x=0 ; x<Minutes ; x++)
				Seconds -= 60;
		}
		else
			Minutes = 0;
	}

	cout << "Found " << Counter << " Prime Numbers in "
		 << Minutes << " minutes and " << Seconds << " Seconds." << endl;
	system("pause");

	delete[] NumberArray;
}

Again it was quick and dirty so probably a little rough around the edges.