Prime number program to make go faster

[divagoddess]

// I am having problems trrying to get my program run faster according to the chart where you run it. I need the program to run less than 10 seconds or even between 10 and 150 seconds for 500000


//This program finds all prime numbers greater than 1 and less than limit.
//(see variable limit below)
//Note that this particular version of the program is not very efficient.
//
//The instructor has written 5 versions, named "Slow" to "Fastest".
//Note that this program is the one called "Slow".
//The following table shows the time taken in seconds for each version
//for different limits.
//
// Limit
//Version 500,000 5,000,000 50,000,000
//------------------------------------------------
//Slow 251.00 too long too long
//Medium 153.00 too long too long
//Fast 1.00 20 498
//Faster 0.37 5 69
//Fastest 0.11 2 19
//
//The next table shows the number of primes found for different limits
//Use this table to make sure your program is producing the right number
//of primes
//
//Limit Number of Primes
//
//50,000,000 3,001,134
// 5,000,000 348,513
// 500,000 41,538
// 50,000 5,133
// 5,000 669
// 500 95
// 50 15
// 5 2
//Note that for limit 5, the program finds only 2 primes: 2 and 3.
//It does not find 5 because with a limit of 5, it only checks numbers 1-4.

#include <iostream>
#include <sys/timeb.h>

using namespace std;



//limit is the number of numbers to check for primeness
unsigned long int limit = 50000;



//This function checks to see if a number is prime
//It does this by dividing the number (number) by every smaller number (i)
//If the function finds an i that divides in evenly into number
//it returns false, otherwise it returns true
//Note that while this function does work, it is VERY slow.
bool isPrime( int x)
{

bool prime = (x > 1); //for numbers >= 2, init prime to true .
//for numbers < 2, init prime to false

// For loop runs as long as i is less than number and
// no i's have divided evenly into number (yet)
for (unsigned long int i=2; i < x / 2 + 1 && prime; x++)
{
//check for primeness by finding the remainder of number
//divided by i (number % i). The result is ANDED with prime.
//If the result is 0, prime becomes FALSE.
prime = prime && x % i;
if (i!= 2)
{

i++;
}
}

//return prime
return (prime);
}





//This function is a time keeping function
//Get the current "tick" count.
//Returns the number of "ticks" since 1/1/1970.
//A tick is 1/1000 of a second.
unsigned long int ticks()
{
unsigned long int tocks;
_timeb currTime; //create a variable of type _timeb
_ftime(&currTime); //get the current time

tocks = currTime.time; //currTime.time contains seconds since 1/1/1970
tocks *= 1000; //mulitply by 1000 to convert to ticks
tocks += currTime.millitm; //add in ticks
return tocks; //return # of 1/1000 seconds since 1/1/1970.
}



//main function
int main()
{
int x;
unsigned long int i, total, start, end;
//i is a counter variable
//total is used to count the number of primes found
//start is used to record the start time in 1/1000 of a second
//end is used to record the end time in 1/1000 of a second

//start time
start = ticks();

//init total to 0
total = 0;

//FOR LOOP
// init as long as add 1
// i to 1 i < limit to i
for (i=1; i<limit; i++)

{
x = (1 / 2)+ 1;
if (isPrime(i)) //check if i is prime
{
total++; //add one to total if number i is prime
}
}

//end time
end = ticks();

//display message
cout <<
"Program checked numbers from 1 to " << limit - 1 << endl <<
"It ran for " <<
(end-start) / 1000.0 <<
" seconds and found " <<
total <<
" prime numbers" <<
endl;


return 0;
}

[divagoddess]

If any body can help me I greatly appreciate it I wriiten the code but its not working

[nspils]

What is happening?

Are you getting error messages? If so, what messages?

Is it running forever?

What does your program do when it reaches a number which exceeds the system's capacity to represent as an int before it gets to the 50,000th prime number?

[divagoddess]

No I am not getting error messages it just that it s not running faster I need it to run less than 10 seconds for an "A" or between 10 to 150 seconds for a "B". I am checking for 500000 which is suppose to output the seconds and also the number of primes.

[nspils]

Were you provided the algorithm for calculating the prime or did you come up with it yourself? There are some very efficient prime number calculation algorithms ... you can do a Google search for them

[divagoddess]

The proesssor gave the C++ code in which we have to modify it to run faster. his worked at a slow speed. I just added x=i/2+1 but it gives me a speed of 43 for 500,0000 i need to get it lower.

[jonnin]

Is prime is way too complex.
you should only test up to the square root of the number.
you should only test one even number (2).
you can test with (num%test == 0 ) -- when this is true, then num is not prime
Completely re-write this function and see if you can make it better.

also your main loop should not feed the isprime dumb numbers that you KNOW are not prime. It fails fast (or will when written properly), but function call overhead is a nasty price to pay for a poor input. At the VERY least you should do a += 2 as even numbers are NOT prime (except 2).

which brings up the main point of the exercise: when provided a junky function, its usually better to re-write it than to try to fix it.

[jonnin]

By the way for such low numbers, the print statements to display all the primes you found should take longer than the processing. If not, something is wrong.

[drkybelk]

Hi,
one great way to reduce the number of tests you have to perform, is to maintain a list of theprime numbers you already found and only test your new numbers for divisability by numbers in that list. The number of primes to be found in the interval [0..n] is O(log(n)), which should vasly improve your perfomance. Mind you: if memory is a concern than this could be a problem, because you have a growing list of primes...
Cheers,

Dieter

[Ivan**]

Hi,
You can also optimize the for loop for speed by using the register keyword like
for (register int i= ; i<limit;++i)

This will put the variable i in the processor's registers instead of on the stack which is faster

[jonnin]

Sometiems Ivan. .NET ignores this suggestion entirely (or older versions do) while other compilers do it sometimes and ignore it others. However one thing you can say for sure is that once the algorithm is good the compiler settings can be tweaked to get better speed.

[Ivan**]

Hi,
Yes, the compiler can ignore the register keyword if there are no free registers. This primarily happens in complex functions because they are more likely to use all the registers. However one good thing about C++ compilers is that it lets you use inline assembly in your C++ functions so you can write the loops using assembly and you only need 4-5 asm instructions for that so if speed is of great importance to you you may consider using inline assembly.

Regards Ivan

[thebeave10]

This code takes 2 seconds to find primes with a limit of 5,000,000 on my PC

#include <iostream>
#include <sys/timeb.h>
#include <math.h>

using namespace std;

unsigned long limit;

unsigned long ticks()
{
unsigned long tocks;
_timeb currTime;
_ftime(&currTime);

tocks = currTime.time;
tocks *= 1000;
tocks += currTime.millitm;
return tocks;
}

int main()
{
	unsigned long x, i, primeCount, start, end, Sqrt;
	unsigned long * primes;
	bool prime;
	
	try {
		primes = new unsigned long [3100000];
	}
	catch (std::bad_alloc&) {
		cout << "Oh No!" << endl;
		return 1;
	}
	limit = 5;
	while (limit <= 5000000) {
		start = ticks();

		primeCount = 0;
		x = 2;
		if ((x % 2) == 0)
			prime = true;

		if (prime)
			primes[primeCount++] = x;
		
		for (x=3;x < limit; x+=2) {
			prime = true;
			Sqrt = (unsigned long) sqrt(x);
			for (i=0;i <= primeCount; i++) {
				if (x % primes[i] == 0) {
					prime = false;
					break;
				}
				if (primes[i] > Sqrt) 
					break;
			}
			if (prime) {
				primes[primeCount++] = x;
			}
		}
		end = ticks();

		cout << primeCount << " primes found with a limit of " << limit << endl;
		cout << "It ran for " << (end-start) / 1000.0 << " seconds" << endl << endl;

		limit *= 10;
	}
	
	delete[] primes;
	
	return 0;
}