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

---

How about a lookup table? :D Search the forum for prime numbers, there are tons of posts on the topic.

Quzah.

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

---

If your interested in making a faster test then read this...
http://mathworld.wolfram.com/FermatsLittleTheorem.html

> 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.

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.

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.

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

That wasn't Salem's point. Note the difference between the code he posted and yours:

Quote:

---

Originally Posted by MadCow257

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.
[edit] Heh, nevermind. You got it. ;)

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?

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.

I never even thought about that scribbler. Thanks for the clarification.

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