Is this C++ naive primality test done right?

Question

Here's my C++ code:

bool isPrime(double value) {
    if (value == 2)                    // ensure 2 returns true
        return true;
    else if (value <= 1)               // eliminate 1 and all negative numbers
       return false;
    else if (fmod(value, 2) == 0)      // eliminate all even numbers
       return false;

    for (int i = 3; i < sqrt(value); i++) {
        if (fmod(value, i) == 0) {
            return false;
        }
    }

    return true;
}

This function should return true if a number given by value is a prime, and false if a number given by value is a composite. First off, I just want to make sure it works correctly, is fairly efficient (it doesn't have to be the best, but I would like it to be decent for a naive approach), and that the code looks nice.

Thanks!

Answer 1

Is there such a thing as a prime real number?

If not then the function signature should use integer (preferably unsigned as there are no negative primes).

Then you should be able to use % rather than fmod() which I would suspect is a tad faster but, more importantly, easier to read.

Since you have already checked for all even primes:

for (int i = 3; i < sqrt(value); i+=2) {
                            //   ^^^^  No need to increment by 1;
                            //         All evens already checked already so inc by 2
                            //         So just check 3/5/7/9 etc

Here is a link to cool but not obvious optimization (That allows you to avoid checking all multiples of 3 as well as 2): https://codereview.stackexchange.com/a/7342/507

Answer 2

2 things:

1. isPrime(9) returns true because you're using < in the loop's termination clause instead of <=.
2. You don't need to add a special case for eliminating even numbers, you can just change the loop's starting point to 2 instead of 3.

for(int i = 2; i <= sqrt(value); i++) {

Answer 3

I suggest the follow edits:

1. Deal only with int (or could use long, but does not change basic algorithm). This allows use of regular modulo operator (%).
2. Could take sqrt(value) out of the loop, but not needed for performance since the C++ compiler has plenty of information to optimize it for you.
3. Instead of just a cast for sqrt, use floor (same effect, but more intent revealing)
4. No explicit test is needed for 2 - it returns true.
5. Skip by 2 in loop.
6. Improved comments.
7. Fixed logic flaw with < sqrt which should be <=

With the resulting code:

bool isPrime(int value)
{
   if (value < 2)      // 2 is smallest prime number
      return false;

   // at least one factor guaranteed to appear before sqrt(x) if x is composite
   for (int i = 3; i <= int(floor(sqrt(value))); i += 2) 
   {
      if (value % i == 0)
         return false;
   }

   return true;
}

This is entirely a style thing, but could also tighten to the following, which looks less cluttered:

bool isPrime(int value)
{
   // 2 is smallest prime number
   if (value < 2) return false;

   // at least one factor guaranteed to appear before sqrt(x) if x is composite
   for (int i = 3; i <= int(floor(sqrt(value))); i += 2) 
      if (value % i == 0) return false;

   return true;
}

Answer 4

If you check for primes a lot, use memoisation to avoid checking values more than once. I would also pre-cache some results and make PrimeCheck class a singleton.

#include <cmath>
#include <unordered_map>

typedef std::unordered_map<int, bool> IntBoolMap;

class PrimeCheck {
public:
    PrimeCheck();

    bool isPrimeCached(int value);

    static bool isPrime(int value);

private:
    IntBoolMap checked_;
};

PrimeCheck::PrimeCheck() {
   checked_[1] = false;
   checked_[2] = true;
   checked_[3] = true;
   checked_[4] = false;
   //pre-populate a few results here
}

bool PrimeCheck::isPrimeCached(int value) {
   IntBoolMap::iterator it = checked_.find(value);
   if (it != checked_.end()) {
      //result found
      return it->second;
   }
   bool result = PrimeCheck::isPrime(value);
   checked_[value] = result;
   return result;
}

bool PrimeCheck::isPrime(int value) {
   if (value < 2) return false;

   int max = static_cast<int>(floor(sqrt(value)));
   for (int i = 3; i <= max; i += 2) {
      if (value % i == 0) return false;
   }

   return true;
}

Answer 5

I would start by removing the sqrt(value) from the loop condition check. You do not want to compute the square root every time as this will not change for the whole of the computation. Compute the root once, round it up and cast it to an int value.

As pointed by Seand, you need to check the equality to the square root, otherwise you might end up with a false positive with that value.

You do not need to check for multiples of 2 and then start the loop at 3. Remove the extra check and start the loop at 2.

Answer 6

One inefficiency I will eliminate for you is the test against the sqrt because you are calculating the square root every iteration.

Calculcate it once.

for( int i = 3, const iMax = static_cast<int>(sqrt(value)); i<=iMax; i+=2 )
{
   // check
}

Of course fmod is potentially less efficient than converting your value to an int once then using % to check for mod.