C++ Program to find Prime Number or Not using For Loop
Before going to the program for Prime Number or Not first let us understand what is a Prime Number?
Prime Number:
A Prime Number is a number greater than 1 and which is only divisible by 1 and the number itself.
For example,
19 is a Prime Number because 19 is not divisible by any number other than 1 and 19.
To find whether a Number is Prime Number or Not it is enough to check whether ‘n’ is divisible by any number between 2 and √n. If it is divisible then ‘n’ is not a Prime Number otherwise it is a Prime Number.
Related: C Program to display Prime Numbers between Two Intervals
Program code for Prime Number or Not in C++:
/* Prime Number or Not */ #include<iostream.h> #include<conio.h> #include<math.h> void main() { int n, flag=0; clrscr(); cout<<"Enter a positive integer value: "; cin>>n; /* Loop to check whether 'n' is divisible by any number between 2 and sqrt(n) */ for(i=2; i<=sqrt(n); i++) { if(n%i==0) { flag=1; break; } } /* if else condition to print Prime Number or Not */ if (flag==0) cout<<n<<" is a prime number."; else cout<<n<<" is not a prime number."; getch(); }
Related: Prime number or Not in C++ using While Loop
Working:
- First, the computer reads the positive integer value from the user.
- Then using for loop it checks whether ‘n’ is divisible by any number between 2 and √n.
- Finally, the if else condition is used to print whether the number is a prime number or not.
Step by Step working of the above Program Code:
For Prime Number:
- Let us assume that a user enters the positive integer value as 19.
- It assigns the value of flag=0, n=19.
- It assigns the value of i=2 and the loop continues till the condition of the for loop is true.
3.1. i<=sqrt(n) (2<=√19) for loop condition is true
n%i==0 (19%2==0) if condition is false
i++ (i=i+1) So i=3
3.2. i<=sqrt(n) (3<=√19) for loop condition is true
n%i==0 (19%3==0) if condition is false
i++ (i=i+1) So i=4
3.3. i<=sqrt(n) (4<=√19) for loop condition is true
n%i==0 (19%4==0) if condition is false
i++ (i=i+1) So i=5
3.4. i<=sqrt(n) (5<=√19) for loop condition is false
It comes out of the for loop.
- flag==0 (0==0) if condition is true
So it prints, 19 is a prime number.
- Thus program execution is completed.
For Not a Prime Number:
- Let us assume that a user enters the positive integer value as 18.
- It assigns the value of flag=0, n=18.
- It assigns the value of i=2 and the loop continues till the condition of the for loop is true.
3.1. i<=sqrt(n) (2<=√18) for loop condition is true
n%i==0 (18%2==0) if condition is false
i++ (i=i+1) So i=3
3.2. i<=sqrt(n) (3<=√18) for loop condition is true
n%i==0 (18%3==0) if condition is true
It assigns flag=1
breaks the loop and comes out of the for loop
- flag==0 (1==0) if condition is false
So it goes to the else part and prints 18 is not a prime number.
- Thus program execution is completed.