In this example, we will write a C++ program to check whether the number entered by the user is a prime number or not.
we will determine the prime number by using:-
The number which will divide by only 1 or itself is called a prime number. for example, 2 3 5 7 11 13 17, etc. are prime numbers.
Now let's see the prime number program in C++. In this program, we will take input from a user and check the prime number using for loop.
#include<iostream>
using namespace std;
int main()
{
int num, i, flag = 0;
cout<<"Enter the Number: ";
cin>>num;
if(num == 0 || num == 1){
flag=1;
}
for(i = 2; i <= (num / 2); i++)
{
if(num % i == 0)
{
flag = 1;
break;
}
}
if(flag == 0)
cout<<num<<" is a Prime Number"<<endl;
else
cout<<num<<" is a not Prime Number"<<endl;
return 0;
}
Enter the Number: 13 13 is a Prime Number
Enter the Number: 6 6 is a not Prime Number
In this program, you have taken input from a user and stored it in a variable say num.
now check if num is 0 or 1 then set the flag=1.
Iterate the loop from 2 to (n/2). inside loop use if-statement for checking whether the remainder is zero. if the remainder is zero then set flag=1
after the end of a loop, check if flag=1 then the print number is prime, if flag=0 then else part will get executed and print number is not a prime number.
This program is the same as above only here we will determine whether the number entered by the user is a prime number or not using a while loop.
#include<iostream>
using namespace std;
int main()
{
int num, i=2, flag = 0;
cout<<"Enter the Number: ";
cin>>num;
/* 0 and 1 is not prime number */
if(num == 0 || num == 1){
flag=1;
}
while(i <= (num / 2))
{
if(num % i == 0)
{
flag = 1;
break;
}
i++;
}
if(flag == 0)
cout<<num<<" is a Prime Number"<<endl;
else
cout<<num<<" is a not Prime Number"<<endl;
return 0;
}
The output of this program is the same as above
In this example, we will write a C++ program for determining prime numbers using the do-while loop. the output will same as the above two programs.
/* check prime number using do while loop */
#include<iostream>
using namespace std;
int main()
{
int num, i=2, flag = 0;
cout<<"Enter the Number: ";
cin>>num;
/* 0 and 1 is not prime number */
if(num == 0 || num == 1){
flag=1;
}
do
{
if(num % i == 0)
{
flag = 1;
break;
}
i++;
} while(i <= (num / 2));
if(flag == 0)
cout<<num<<" is a Prime Number"<<endl;
else
cout<<num<<" is a not Prime Number"<<endl;
return 0;
}
Since we have iterated the loop till n/2 in all the above programs. therefore, the time complexity of all the above programs will be O(n)/2.