TO CHECK WHETHER THE GIVEN NUMBER IS PRIME NUMBER OR NOT

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.

See also  SELECTION SORT ALGORITHM

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.

See also  THE GIVEN NUMBER IS ARMSTRONG OR NOT

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!

Leave a Comment

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

we provide projects, courses, and other stuff for free. in order for running we use Google ads to make revenue. please disable adblocker to support us.