# optimise algorithm

• 01-18-2005
cyberCLoWn
optimise algorithm
I have written a program which tests for prime numbers. Please could someone review my code and tell me if there is any way to optimise it as once you start hitting large numbers it takes that much longer to break the loop and return a result.

Code:

```int prime( long unsigned int &number ) {   int factor = 0;     for( int i = 1; i <= number; i++ )       if( number % i == 0 )// if there is no remainder - i is a factor of number         factor++;     if( number == 1 )       return 1;   else if( factor == 2 ) // number is prime if only 2 factors are found       return 1;   else // more than two factors found, number is not prime       return 0;      } // end function prime```
• 01-18-2005
quzah
How about a lookup table? :D Search the forum for prime numbers, there are tons of posts on the topic.

Quzah.
• 01-18-2005
The code below is a very obvious optimization, there are definitely more things that could be optimized if you need more speed.
Code:

```#include <math.h> int prime( long unsigned int &number ) {         if (number % 2 == 0)         {                 cout << "Number is not prime\n";                 return 0;         }         for (int i = 3; i <= sqrt(number); i=i+2)         {                 if (number % i == 0)// if there is no remainder - i is a factor of number                 {                         cout << "Number is not prime\n";                         return 0;                 }         }         cout << "Number is prime\n";         return 0; }```
http://mathworld.wolfram.com/FermatsLittleTheorem.html
• 01-18-2005
Salem
> for (int i = 3; i <= sqrt(number); i=i+2)
Which is even worse than the original - now you're doing square root on every iteration of the loop.

Code:

```int limit = sqrt(number); for (int i = 3; i <= limit; i=i+2)```
Also, you can do better that +2 each time.
3 5 7 9 11 13 15 17
You only need check numbers which are known to be prime already - it's a waste of time checking 9 and 15, because these are already a multiple of 3, so any multiple of 9 will by definition also be a multiple of 3, and therefore always composite.
• 01-18-2005
The first point about the sqrt is important, however, dividing by only primes is harder then one might think. If you use an array to mark out multiples then you are limited to numbers in the int region, because too much larger then 2^32 and you won't have the RAM. Anyways, computers are fast enough these days that checking primality on a number as small as an int is very fast on even unoptimized code, which makes dividing by primes even less attractive.
• 01-18-2005
cyberCLoWn
Right, I'll definitely look into the above mentioned optimizations. Thanks so much.

What did you mean by this though?
Quote:

Also, you can do better that +2 each time.
What do the -O1 through to -O3 optimizations actually do? What is the difference behind them and which one do you pick? I use the Dev-C++ compiler.
• 01-18-2005
Scribbler
Quote:

Originally Posted by Salem
> for (int i = 3; i <= sqrt(number); i=i+2)
Which is even worse than the original - now you're doing square root on every iteration of the loop.

Actually, using (int i = 3; i <= sqrt(number); i=i+2) is much more efficient.

As a comparison (this is a typical learning project) checking for all primes in the range 1 - 10,000, using the formula n/2 results in 1,415,016 calculations, whereas using sqrt[n] results in 55,958 calculations.

Since the OP has already done the footwork for the project, I'll attach the code I used as a comparison...

[EDIT] ne'r mind...I just realized you were saying to get the square root before entering the loop each time. Still on my first cup o java :D
• 01-18-2005
pianorain
That wasn't Salem's point. Note the difference between the code he posted and yours:
Quote:

Code:

`for (int i = 3; i <= sqrt(number); i=i+2)`

Quote:

Originally Posted by Salem
Code:

```int limit = sqrt(number); for (int i = 3; i <= limit; i=i+2)```

You don't want to recalculate that square root every iteration through the loop. It's expensive and wasteful.
 Heh, nevermind. You got it. ;)
• 01-18-2005
cyberCLoWn
Right, I agree about the sqrt() being done once outside the loop. Still, why is int i in the for loop incremented by 2 each loop?
• 01-18-2005
Scribbler
Quote:

Originally Posted by cyberCLoWn
Still, why is int i in the for loop incremented by 2 each loop?

Because other than the number 2, there are no even numbers that will be prime, so incrementing by 2 will keep you limited to odd numbers.
• 01-18-2005
cyberCLoWn
I never even thought about that scribbler. Thanks for the clarification.

So, what do I do about the optimization flags? (-01, etc)