Search code examples
c++primessqrt

while (i<=sqrt(static_cast<double>(n))

In the "C++ Without Fear: A Beginner's Guide That Makes You Feel Smart" book, in Chapter (2): Decisions, Decisions, you can see this lin of code as part of the prime number program:

while (i<=sqrt(static_cast<double>(n))

Provided that "i" was initialized to "2", and "n" is the user's input.

Why are we comparing to the "sqrt" of "n" and not to "n" itself?

Thanks.

Solution

  • Because if a number has factors other than itself and 1, then at least one of those factors will be less than the number's sqrt.