Prime number program to make go faster


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 13 of 13

Thread: Prime number program to make go faster

  1. #1
    Join Date
    Apr 2006
    Posts
    5

    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.
    //
    // 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;
    }

  2. #2
    Join Date
    Apr 2006
    Posts
    5
    If any body can help me I greatly appreciate it I wriiten the code but its not working

  3. #3
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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?

  4. #4
    Join Date
    Apr 2006
    Posts
    5
    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.

  5. #5
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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

  6. #6
    Join Date
    Apr 2006
    Posts
    5
    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.

  7. #7
    Join Date
    Dec 2003
    Posts
    3,366
    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.

  8. #8
    Join Date
    Dec 2003
    Posts
    3,366
    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.

  9. #9
    Join Date
    Jan 2005
    Location
    UK
    Posts
    604
    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

  10. #10
    Join Date
    Apr 2006
    Location
    Zagreb, Croatia
    Posts
    152
    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

  11. #11
    Join Date
    Dec 2003
    Posts
    3,366
    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.

  12. #12
    Join Date
    Apr 2006
    Location
    Zagreb, Croatia
    Posts
    152
    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

  13. #13
    Join Date
    May 2006
    Posts
    1
    This code takes 2 seconds to find primes with a limit of 5,000,000 on my PC

    Code:
    #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;
    }

Similar Threads

  1. how to make select distinct faster
    By in forum Database
    Replies: 1
    Last Post: 08-28-2002, 01:29 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center