C++: Check for Prime Number

So, what's a prime number? Basically, its a number that is not divisible by any other number. i.e, a number n is said to be prime if it is indivisible. No, this may not be the generic mathematical definition and I'm not good in giving out solid definitions but you know how it is, right?

Now, the big question. How do you check for a prime number in C++? The logic is very simple and so is the code. You just got to use the right check -- the modulus (%) operator.

Source Code

#include<iostream>
#include<stdlib.h>
#include<process.h>
using namespace std;
void main()
{
	system("cls");
	//We don't consider negative numbers. Hence, unsigned.
	unsigned int i,num,flag=1;
	cout<<"\nEnter the number: ";
	cin>>num;
	if(num==1)
	{
		cout<<"\n\n1 is not prime.\n";
		system("pause");
		exit(0);
	}
	for(i=2;i<=num/2;i++)
	{
		if(!(num%i))
		{
			flag=0;
			break;
		}
	}
	if(flag)
		cout<<"\n\n"<<num<<" is prime."<<'\n';
	else
		cout<<"\n\n"<<num<<" is not prime. It is divisible by "<<i<<'\n';
	system("pause");
}

Analysis

The modulus operator as you might know returns the remainder of the division expression. So, if a number got to be prime, it should be indivisible i.e, the remainder of the expression can never be zero. If it were zero, this indicates that the number is divisible by the given divisor. But how far should we check? We can check through all the way upto when the iteration variable, i.e, i here will reach a maximum limit of num-1. However, is it really necessary? Its obvious that beyond num/2, no number can divide num to parts. Thus, by checking through the values past num/2, we are simply wasting the time. Since it is already known to us and is obvious, we check only upto num/2 saving the compilation time.

So, we first give a condition to check whether the given number is 1 as 1 is neither prime nor composite (special case) and then go to the main block. Here, a loop drives the program and the loop variable, i.e i here takes different values and checks each case whether the remainder of num/i is 0. If it gets a 0, the loop ends there and gives an output that the number isn't prime. Else, the program carries on till it reaches i=num/2 after which the loop dies and hence, the number can be declared prime. Note that flag variable is used to differentiate the two conditions. You can use an exit() function too instead of giving a flag variable.

So, wasn't that easy? Now, take this challenge. Build a program that can print the first n prime numbers. Think you can do it? Let us see if you are faster than my next post. ;)