# TO CHECK WHETHER THE GIVEN NUMBER IS PRIME NUMBER OR NOT￼

## 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.