Understanding the 'Prime Number Test' code.

[apprentice01]

Hello everybody,

I have just recently started learning C++ and I have come across my first hurdle. I have read, and re-read, researched online, but to no avail: I'm unable to comprehend how the code works and why it does. If someone would be kind enough to explain each step of the code, the reason it's there, the function of the statement, etc. it would be immensely appreciated!

Cheers,
Apprentice01 (Using Dev-C++ on WinXP)

#include <iostream>
#include <math.h>
using namespace std;

int main(){
int n, i, is_prime;

is_prime = true;

cout << "Enter a number to test primeness: ";
cin >> n;

i = 2;
while (i <= sqrt(static_cast<double>(n))){
if (n % i == 0)
is_prime = false;
i++;
}

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

[Ganon11]

#include <iostream>
#include <math.h>
using namespace std;
 
int main(){
   int n, i, is_prime;
 
   is_prime = true;
 
   cout << "Enter a number to test primeness: ";
   cin >> n;
 
   i = 2;
   while (i <= sqrt(static_cast<double>(n))){
      if (n % i == 0)
         is_prime = false;
      i++;
   }
 
   if (is_prime)
      cout << "Number is prime.";
   else
      cout << "Number is not prime.";
   return 0;
}

OK, I'll assume you know what all the variable declarations are about, so I'll skip to the while loop.

A number is prime if its only divisors are 1 and itself (because, for any number N, N/1 == N and N/N == 1. If a number m is a divisor of n, that means there exists an integer c such that m * c == n (For example, 5 is a divisor of 15 because 3 * 5 == 15. n is 15, m is 5, and c is 3 in this example). The largest number that could possibly be a divisor of n is the square root of n (because any larger than this multiplied by an integer is either less than n (if c == 1) or greater than n (for c > 1). So you only need to check from 2 to sqrt(n) for divisors.

This is exactly what your loop does. It checks if i is a divisor of n by seeing if the remainder after integer division is 0 (that's the % statement). It also makes i all values between 2 and sqrt(n). If there is ever a number i that divides evenly into n (i.e. n % i == 0), then i is a divisor of n. Since i cannot be 1 (we start at 2 and increase) and i cannot be n (we stop at sqrt(n) < n), n cannot be prime.

Anything else you're not getting? This is mostly mathematics, not programming.

[apprentice01]

Thank you for the explanation! Will pursue my studies with the new light that has been shed!