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.
DamianZ98 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
7
Is crucial for efficiently checking.
The while loop iterates through potential divisors of n starting from 2 up to sqr(n). Being this an efficient way to test for primality because: [1] Instead of checking all numbers from 2 to n-1, checking up to sqr(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). And [2] By checking all posible divisors up to sqr(n) you ensure that if n is composite, you will find a divisor within this range and if no divisors are found, 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 sqr(n)