INTRODUCTION
Given an integer n, write a program TO CHECK WHETHER THE GIVEN NUMBER IS PRIME NUMBER OR NOT
Ex1:
Input N: 11
Output: Prime Number Some more prime numbers are 2,3,5,7,11,13,17,19,23,29,31,37,41,43 and so on.
APPROACH1
A prime number is a natural number which is only divisible by 1 and itself. So if we divide the number by running a loop from 2 and one less than the given number, if anywhere the number resulted in the remainder of zero, then it is not a prime number. Otherwise, it is a prime.
ALGORITHM
STEP 1: start
STEP 2: take the input value of n.
STEP 3: divide the input number by checking whether the given number is divisible from 2 to a number less than the input number.
STEP 4: if the remainder resulted in zero, increment the count value
STEP 5: if the number is greater than 1 and the count value is equal to zero, then the number is a prime number. Otherwise, it is not a prime number
STEP 6: stop.C++ Code:
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,count=0;
cin>>n;
for(int i = 2 ; i<n ; i++) {
if(n%i == 0)
count++;
}
if( n>1 && count == 0)
cout<<"Prime number";
else
cout<<"Not a prime number";
}
Python code:
n = int(input())
count = 0
for i in range(2,n):
if n%i == 0:
count=count+1
if n>1:
if count == 0:
print("Prime number")
else:
print("Not a prime number")
JAVA code:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int count = 0;
for(int i = 2 ; i<n ; i++) {
if(n%i == 0)
count++;
}
if( n>1 && count == 0)
System.out.println("Prime number");
else
System.out.println("Not a prime number");
}
}
Input: 11
Output: Prime number
The time complexity of the code is O(n) as here we use a for loop.
The space complexity of the code is O(1).
APPROACH 2:
Applying the above same logic but iterating the loop from 2 to less than or equal to the square root of the given number, results in decreased time complexity of the code.
ALGORITHM
STEP 1: start
STEP 2: take the input value of N.
STEP 3: divide the input number by checking whether the given number is divisible from 2 to a number less than or equal to the square of the input number.
STEP 4: if the remainder resulted in zero, increment the count value
STEP 5: if the number is greater than 1 and the count value equals zero, then the number is a prime number. Otherwise, it is not a prime number
STEP 6: stop.C++ Code:
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,count=0;
cin>>n;
for(int i = 2 ; i<=sqrt(n) ; i++) {
if(n%i == 0)
count++;
}
if( n>1 && count == 0)
cout<<"Prime number";
else
cout<<"Not a prime number";
}
Python code:
import math
n = int(input())
count = 0
m = int(math.sqrt(n))
for i in range(2,m+1):
if n%i == 0:
count = count+1
if n>1:
if count == 0:
print("Prime number")
else:
print("Not a prime number")
JAVA code:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int count = 0;
for(int i = 2 ; i<=Math.sqrt(n) ; i++) {
if(n%i == 0)
count++;
}
if( n>1 && count == 0)
System.out.println("Prime number");
else
System.out.println("Not a prime number");
}
}
Input: 1234
Output: No. Of digits in the number: 4
The time complexity is O(√n) and the space complexity of the code is O(1).CONCLUSION
That’s it from this tutorial. I hope you guys found It interesting. We have solved the problem to check whether the given number is a prime number or not in different programming languages.
In the next article, we are going to see how to reverse a given number with solution codes in c++, java and python.
Happy coding!
