3 Ways to Find Prime Number

In this post we will see 3 different java codes to check a given number is prime or not.

What is Prime Number

A number is said to be prime if it is not divisible by any other number except 1 and itself.

So if a given number is not divisible by any other number except 1 and number itself we call it as prime number otherwise its not a prime number.

NOTE :

2 is the only even prime number.

Example:

Example 1:

Number N=5

As 5 is not divisible by any other number between 1 and 5 (number > 1 and number <5). Then we call 5 asa prime number.

Example 2:

Number N=8

Factors of 8 are 2, 4, which means 8 is divisible by 2 and 4, so 8 is not a prime number.

Logic to Decide a number is prime or not

There are 3 logics for finding a number is prime or not, they are differing interms of execution time so first logic takes more time compared to second and second takes more time compared to third

Overall we cany say 3rd logic is optimised

Logic 1:

Take a number for which you wish to find prime or not, let us say N
Initialize a counter to ZERO, at the end we will check counter if it’s exactly equal to 2 then it’s a prime number otherwise it’s not a prime number.
Run a loop for dividing a number starting from 1 upto N.
Each time the remainer of division is ZERO, which means completely divisible increase the counter by 1.
At the end check for counter value and decide according to step 2

Java Code for Logic 1

package arrayproblems;

import java.util.Scanner;

public class primeNumber1 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the number ");
		int N= sc.nextInt();
		
		int count=0;
		for(int i=1;i<=N;i++) {
			
			if(N%i==0) {
				count=count+1;
			}
		}
		if(count==2) {
			System.out.println("The given number is prime");
		}
		else {
			System.out.println("The given number is not prime");
		}
		

	}

}

Also Read

Java Code for Fibonacci Series

Logic 2:

Logic 2 is same as that of logic 1 except here we don’t consider 1 and number itself for division
which will reduce 2 extra steps in our code
Take the input let us say N
initialize a counter to zero
Run a for loop starting from 2 upto N-1.
Check if counter>0, if true break the loop as it assures that given number is not a prime number.
check if N is completely divisible by numbers between 2 and N-1, if yes increment counter by 1
at the end, if counter ==0, then it’s a prime.

Java Code for logic 2

package arrayproblems;

import java.util.Scanner;

public class primeNumber2 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the number");
		int N= sc.nextInt();
		
		int count=0;
		for(int i=2;i<N;i++) {
			
			if(N%i==0) {
				count=count+1;
			}
			
			
		}
		if(count==0) {
			System.out.println("Given number is prime");
		}
		else {
			System.out.println("Given number is not a prime");
		}

	}
		
}

Also Read

J ava code for finding factors of a Number

Logic 3:

This is logic is most optimised one, Generally if we observe the factors of any number they lie between 1 to N/2. which means if n=4 then factors for 4 are 1 and 2. Here 2 is the highest factor which is equal to 4/2=2 (N/2).

Similrarly

factors of 6 are 1, 3, here also highest factor is 3 and it is eual to 6/2 (N/2) or roughly sqrt(6).

Another example

factors of 10 are 1, 5, here also highest factor is 5, that is equal to 10/2 (N/2) or roughly sqrt(10).

So from above discussion we can say there is no need to run the loop untill N as all the factors of N will be present with N/2.

Which will reduce execution time to greater extent.

STEPS

Take the number let us say N
initialize a counter to Zero
Run a loop starting from 2 utp N/2 or sqrt(N) generally preffered.
if a number completely divides given number N, increment counter by 1
at the end check if counter == 0, true means prime otherwise not a prime.
This algorithm will reduce execution time of program.

Java Code for Logic 3

package arrayproblems;

import java.util.Scanner;

public class primeNumber3 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the number");
		int N= sc.nextInt();
		
		int count=0;
		for(int i=2;i<=Math.sqrt(N);i++) {
			
			if(count>0) {
				break;
			}
			if(N%i==0) {
				count=count+1;
			}
			
			
		}
		if(count==0) {
			System.out.println("Given number is prime");
		}
		else {
			System.out.println("Given number is not a prime");
		}

	}
		

}

What is Prime Number

Leave a Comment Cancel Reply