Prime number program to make go faster
// 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.
//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
//Limit Number of Primes
// 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.
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)
//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.
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 = ticks();
//init total to 0
total = 0;
// 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 = ticks();
"Program checked numbers from 1 to " << limit - 1 << endl <<
"It ran for " <<
(end-start) / 1000.0 <<
" seconds and found " <<
" prime numbers" <<
Last Post: 08-28-2002, 01:29 AM
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL