Using sqrt function within a while loop, don't understand it

Question

I'm currently going through "C++ Without Fear, Third Edition". I'm a little confused with this block of code, I understand how the if statement is used to find out if n is divisible by i. I just don't understand what is the point of the while loop.

Surely, you could just write the code without it and if the if loop comes back with a remainder then it will be a prime number, otherwise it will not be a prime number.

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int n = 0; // Number to test for prime-ness
    int i = 2; // Loop counter
    bool is_prime = true;   // Boolean flag...
                            // Assume true for now

    // Get a number from the keyboard
    cout << "Enter a number and press ENTER: ";
    cin >> n;

    // Test for prime by checking for divisibility
    // by all whole numbers from 2 to sqrt(n).

    while (i <= sqrt(n)){
        if (n % i == 0) {       // If i divides n,
            is_prime = false;   // n is not prime
            break;              // BREAK OUT OF LOOP NOW!
        }
        ++i;                    // Add 1 to i.
    }

    // Print results

    if (is_prime) {
        cout << "Number is prime." << endl;
    } else {
        cout << "Number is not prime." << endl;
    }
    return 0;
}

I don't understand it, please help me.

Answer 1

This is crucial for efficiently checking.

The while loop iterates through potential divisors of n starting from 2 up to sqrt(n). This is an efficient way to test for primality because:

1. Instead of checking all numbers from 2 to n-1, checking up to sqrt(n) reduces the number of iterations; if a number n has a divisor larger than sqr(n), the corresponding co-divisor must be smaller than sqr(n).

2. By checking all possible divisors up to sqrt(n), you ensure that if n is composite, you will find a divisor within this range, and if no divisors are found then n is prime.

If you remove the while loop and just use an if statement, you would need to explicitly list all potential divisors, which is impractical and inefficient. The while loop provides a systematic way to check all necessary divisors up to sqrt(n).