WAP to check the given number is prime or not
Objective
Write a C++ program to check if a given number is Prime.
Algorithm / Approach
- Read an integer
n. - Initialize a
flag = 0. - Run a loop from 2 up to the square root of
n(sqrt(n)). - If
n % i == 0, the number is divisible. Setflag = 1, andbreakthe loop immediately. - Check the flag after the loop to determine if it is Prime.
main.cpp
#include<iostream>
#include<math.h>
using namespace std;
int main() {
int n;
int flag = 0;
cout<<"Enter Value for N: ";
cin>>n;
for(int i =2; i<=sqrt(n);i++) {
if(n%i==0) {
flag = 1;
break;
}
}
if(flag==0) {
cout<< n<<" is a prime no. \n";
}
else {
cout<< n<<" is not a prime no. \n";
}
return 0;
}Expected Output
Enter Value for N: 5 5 is a prime no.
Explanation of the Program
- A Prime number is a number greater than 1 that has no divisors other than 1 and itself.
- Instead of checking every number up to N, mathematically we only need to check up to the square root of N. If a number has a divisor larger than its square root, it MUST also have a corresponding divisor smaller than its square root.
Complexity
Time Complexity
O(√n) - Much faster than O(n).
Space Complexity
O(1)
