HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

Is this C++ naive primality test done right?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thisnaiveprimalitytestdoneright

Problem

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!

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#8667, answer score: 13

Revisions (0)

No revisions yet.