Finding a Prime Number code c++

Question

I have been given the code below, it passes a number to check if it is prime. I do not understand what floor(sqrt(toCheck)) +1 does or what the prbvariable does. I think it runs the while loop while the bool noFactorFound is true and prb is less than searchLimit. Everything would fall into place if I knew how searchLimit was initialised.

#include<cmath> //for floor() & sqrt()

#include "prime.h"

bool isPrime(unsigned toCheck)
{
    if (toCheck== 2)
        return true;
    if ((toCheck % 2) == 0)
        return false;
    unsigned prb = 3;
    unsigned searchLimit = floor(sqrt(toCheck)) + 1;
    bool noFactorFound = true;
    while (noFactorFound && (prb<searchLimit))
    {
        if ((toCheck % prb) == 0)
            noFactorFound = false;
        else
            prb += 2;
    }
    return (noFactorFound);
}

[sqrt()](http://en.cppreference.com/w/cpp/numeric/math/sqrt), [floor()](http://en.cppreference.com/w/cpp/numeric/math/floor) — πάντα ῥεῖ, Nov 19 '15 at 15:52

score 1 · Answer 1 · answered Nov 19 '15 at 15:52

The reason for initialising the search limit to sqrt(N)+1 is that if a number larger than sqrt(N)+1 divides N, then a number less than sqrt(N)+1 would also divide it, as factors occur in pairs (except sqrt(N), which is included in search range).

The sqrt function finds the square root of a number. Floor rounds off a floating number to the greatest integer lower than the float.

The +1 is done to avoid missing out on numbers due to the rounding off by the floor function. An alternative would be to use the ceil function, with no need of the +1.

score 1 · Answer 2 · answered Nov 19 '15 at 15:53

When you are looking for factors of a number you do not need to look for numbers that are larger than the square root of that number. So eventually when we loop we want to only go up as many indexes as the square root.

floor(sqrt(toCheck)) + 1;

This takes the square root of toCheck. However sqrt returns a float and our loop indexes are whole number unsigneds so we take the non-fractional part with floor then add one to it to avoid missing out a factor if that happened via rounding.

Much of this can be figured out by carefully reading the documentation, so I'd advise doing that when faced with similar problems.

Finding a Prime Number code c++

2 Answers2