 Programming tutorials online .NET, Java, C++, Visual Basic, and More Home     General Forum -- Choose Forum -- General Forum .NET Forum Java/J2EE Forum C/C++ Forum VB/VB.NET Forum

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

 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 Email Password  Forgot my password

Search

Featured Book Introducing Microsoft .Net, Third Edition

Featured Software Microsoft Visual Studio Standard 2005 