How check whether a number is prime or not in java.
Given an input integer, write a code to check whether an input number is prime or not.
For example –
Example 1:
Input: 7
output: true
Example 2:
Input: 12
Output: false
In this tutorial, I am going to discuss multiple approaches to solve this problem. Also, we will write it’s java code. At the end of this post, I have shared a link to the video tutorial.
Check whether a number is prime or not video tutorial
Before writing a program, let’s quickly understand what is a prime number.
Prime Number
A prime number is a number that is greater than 1 and it has no positive divisors other than 1 and itself.
For example – 3, 13, 7 is a prime number, as it’s divisible by 1 and itself. Similarly, 29, 19 etc. are also prime numbers.
6 is not a prime number as it’s divisible by 1, 2, 3 and 6.
2 is the only even prime number.
How to Check whether a Number is Prime or not in Java
There are multiple approaches through which we can check whether a number is prime or not.
Method 1
It is the simplest approach to check whether a number is prime or not. In this approach, we run a loop from 2 to n-1 (where n is an input number) and check whether a number is perfectly divisible by any other number other than 1 and itself. If a number is divisible (other than 1 and itself) then it’s not a prime number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//check whether a number is prime or not public static boolean checkPrime(int n) { /* If n is less than or equal to 1, then it's not a prime */ if(n <= 1) { return false; } //Run a loop from 2 to n-1 for( i = 2; i < n; i++) { /*If n is divisible by any other number other than 1 and itself, *then it's not a prime number */ if(n%i == 0){ return false; } } return true; } |
The time complexity of this approach is O(n).
Java program to print Fibonacci series up to N number
Programming questions on linked list
Method 2 –
Let’s improve a method 1. Instead of running a loop from 2 to n-1. We can run a loop to from 2 to n/2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//check whether a number is prime or not public static boolean checkPrime(int n) { if(n <= 1) { return false; } //Run a loop from 2 to n-1 for( i = 2; i <= n/2; i++) { if(n%i == 0){ return false; } } return true; } |
Efficient way to print prime numbers between 1 to N
Method 3 – Most efficient way to check whether a number is prime or not in java
In this approach, we run a loop from 2 to sqrt(n).
Why do we check up to the square root of n to determine whether a number is prime or not?
To understand this concept, let’s take a number n and suppose the value of n is 15. 15 is not a prime number. So the factors of 15 are 3 and 5. The Square root of sqrt(15) is 3.87.
If a number n is not a prime, it can be factored into two factors a and b:
n = a*b
If both the factors a and b is greater than the square root of n. Then the a*b would be greater than n. So at least one of those factors must be less than or equal to the square root of n. To check if a number n is prime, we only need to test for factors less than or equal to the square root.
The time complexity of this approach is O(n1/2)
Check whether a number is prime or not | Java Code
We have compared three approaches and their time complexities. Let’s write a java program to check prime number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.io.*; import java.math.*; public class Solution { public static boolean checkPrime(int n) { /* Run a loop from 2 to sqrt(n) */ for (int i=2; i <= Math.sqrt(n); i++) { /* Check if it is divisible */ if(n%i == 0){ return false; } } return true; } public static void main(String[] args) { System.out.println("Enter a number \n"); Scanner in = new Scanner(System.in); int n = in.nextInt(); if(n>=2 && checkPrime(n)){ System.out.println("Prime"); } else { System.out.println("Not prime"); } } } |
