Programming tutorials online .NET, Java, C++, Visual Basic, and More
 

Home
.NET Tutorials
General Programming Tutorials
Community/Forums
Site Extras

 

General Forum
 

Un-moderated developer's forum for discussing any programming topics, languages, issues or whatever you feel like.


POST REPLY
Posted By: divagoddess   4/25/2006 7:12:00 PM
 
would like some help trying to modify this program to run faster. This current version takes 251 seconds to find the number of prime numbers greater than 1 and less than 50000. How would i make it run less than 251 seconds?

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

using namespace std;



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




//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 number)
{

bool prime = (number > 1); //for numbers >= 2, init prime to true .
//for numbers
// 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 {
//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 && number % 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()
{

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 for (i=1; i {
if (isPrime(i)) //check if i is prime
{
total++; //add one to total if number i is prime
}
}

//end time
end = ticks();

//display message





 
Sign In
Email
Password
  Forgot my password

Search

Featured Book

Introducing Microsoft .Net, Third Edition ($19.79)
Introducing Microsoft .Net, Third Edition


Featured Software

Microsoft Visual Studio Standard 2005 ($249.99)
Microsoft Visual Studio Standard 2005





 
© 2022 Ammastore.org
All Rights Reserved
COMPUTER SCIENCE HOMEWORK | Privacy/Disclaimer