# Is this C++ naive primality test done right?

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!

• I don't know how efficient the implementation is of fmod() on your system, but statements like if ((value & 0x1) == 0) is likely a faster way to detect even numbers. That's possibly the case with fmod() in your for loop as well. You could use if ((value % i) == 0) instead. – Jonathan Wood Feb 6 '12 at 17:55

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

• The optimization is interesting (and clever) but seems to complicate the flow beyond OP goal of a "naive" algorithm. – codingoutloud Feb 6 '12 at 16:01
• @codingoutloud: Your definition of complicated must be different from mine :-) i+=2 => i+=t, t=6-t – Martin York Feb 6 '12 at 16:05
• Hi @Loki Astari - IMHO even that simple change would elicit a WTF from many programmers. It is not obvious - not "naive" - what is going on. Your comment did not include all the changes; the loop initialization is also more complex (and, IMHO, also does not pass the initial WTF/naivity test). I am not saying that nobody can understand it, or that it isn't a good optimization, etc., simply that it doesn't seem to me consistent with the request for a "naive primality test" as specified in the OP. – codingoutloud Feb 6 '12 at 22:17
• @codingoutloud: OK. I can agree with that :-) – Martin York Feb 6 '12 at 22:22

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++) {

• If I change the loops starting point to 2 instead of 3, and I fail to check for 2, with my current implementation, it says that 2 is composite. – Bob Feb 4 '12 at 19:10
• @Bob: No, I was talking about the even numbers only, not the first if statement where you check for 2. – seand Feb 4 '12 at 19:15
• @seand - good catch on the isPrime(9)! adjusted my answer to include that. – codingoutloud Feb 5 '12 at 0:30

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

• It's C++ code, not Java. – seand Feb 5 '12 at 0:29
• Thanks - I updated my syntax and comment - and thanks for the formatting edit to improve visibility of keywords. – codingoutloud Feb 5 '12 at 0:47

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_ = false;
checked_ = true;
checked_ = true;
checked_ = 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;
}

• Couldn't you just cache all the primes and the greatest non-prime found? Assuming that knowing the primeness of n tells you the primeness of n-1 for n >= 3, this could save space and you'd still know all primes. It would lead to lookups being O(lg(n)) instead of O(1), though. – Anton Golov Feb 5 '12 at 11:46
• To generate all the primes up to N, create an array up to N(-1)with factor[x]=x for all values. Then iterate x up to sqrt(N) (xx < N ) with if( factor[x]==x ) // primes only; for( y = x; (factor[y]==y || factor[y]==x) && xy < N ){ factor[x*y]=x; } You end up with a table of the lowest prime factor of every number and a number is prime if its lowest prime factor is itself. – CashCow Feb 7 '12 at 17:48

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.

• I want to say that modern compilers will cache the result of the sqrt call but I'm not sure about that. It's good that you mention it though because caching the value yourself is a good habit to get into for cases where the compiler can't optimize it. – seand Feb 5 '12 at 0:27
• I don't think you''ll find a compiler these days which can't figure out that optimization. But if you leave it in the loop, you will want to cast it since I believe otherwise the compiler will promote your int value to a double to do the comparison each time through the loop. So i < int(sqrt(value)) could go in the loop and be better off from optimization point of view. As I did in my answer, I think that i < int(floor(sqrt(value))) is more intent revealing. – codingoutloud Feb 5 '12 at 0:53

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.