- Prepare
All Platforms Programming Aptitude Syllabus Interview Preparation Interview Exp. Off Campus - Prime Video
- Prime Mock

- Interview Experience
- Prime VideoNew
- Prime Mock
- Interview Prep
- Nano Degree
- Prime Video
- Prime Mock

# Java Program to Check Whether a Number is Prime or Not

## Check Whether a Given Number is Prime or Not in Java

Given an integer input greater than 0. The objective is to Check Whether or Not the Number is a Prime. To do so we’ll write a code to Check Whether a Given Number is Prime or Not in Java that checks for the factors of the Number besides 1 and the number itself.

```
Example
Input : 23
Output : Prime
```

## Write a program to check if a given number is prime or not in java

Given an integer input, the objective is to – Write a program to check if a given number is prime or not in Java. Here are some of the Methods to Check for Prime –

**Method 1:**Simple iterative solution**Method 2:**Optimization by break condition**Method 3:**Optimization by n/2 iterations**Method 4:**Optimization by √n**Method 5:**Optimization by skipping even iteration**Method 6:**Basic Recursion technique

We’ll discuss the above-mentioned methods in detail in the sections below. Check out the Blue box mentioned below to know more about prime numbers.

### Prime No Program in Java

**Method 1:** Simple iterative solution

### Working

In this method, we’ll iterate through all the numbers that lay in the interval [1, number] and check if any of them is a factor of the number, if so it’s not a Prime.

For a given integer input we check for the following,

- If the count of factors for this number is > 2 then
- It’s not prime else it’s prime
- A prime number must only be divisible by 1 and the number itself.

### Java Code

// Time Complexity : O(N) // Space Complexity : O(1) public class Main { public static void main (String[]args) { int n = 23; checkPrime(n); } private static void checkPrime(int n) { int count = 0; // negative numbers, 0 and 1 are not prime if (n < 2) System.out.println ("The given is number " + n + " is not prime"); // checking the number of divisors b/w [1, n] for (int i = 1; i <= n; i++) { if (n % i == 0) count += 1; } // if count of divisors greater than 2 then its not prime if (count > 2) System.out.println ("The given is number " + n + " is not prime"); else System.out.println ("The given is number " + n + " is prime"); } }

### Output

23 is : Prime

**Method 2:** Optimization by break condition

### Working

In the above mentioned we’ll divide the whole loop situation into two parts, we’ll check if the number is lesser than 2, it’s not a prime. It also mustn’t have factors between range [2, num-1]

For an integer input, we check the following,

- If the number is lesser than 2.
- If the number has any factors other than 1 and itself.
- If either of the above two conditions are satisfied, the number is not a Prime.

### Java Code

// Write a java program to check whether a given number is prime or not public class Main { public static void main (String[]args) { int i, n = 13; boolean isprime = true; // 0 and 1 are not prime numbers also, negative numbers are not prime if (n < 2) { isprime = false; } else { for (i = 2; i < n; i++) { if (n % i == 0) { isprime = false; break; } } } String result = isprime ? "Prime" : "not Prime"; System.out.println ("The number " + n + " is : " + result); // Time Complexity : O(N) // Space Complexity : O(1) // This program is better than previous version as : // Condition for 0, 1 and negative numbers checked earlier // Loops runs b/w [2, n-1] rather than [1, n] } }

### Output

13 is : Prime

**Method 3:** Optimization by n/2 iterations

### Working

In this method, we’ll only run the loop until number/2.

As it’s known that the smallest factor of every number if any, will lie in the interval [2, number/2].

For an integer input, we do the following –

- Check if the number is lesser than 2.
- Check if the number has any factors other than 1 and the number itself in the interval [2, number/2].
- If either if the conditions are satisfied, the number is not a Prime.

### Java Code

// Prime no Program in Java public class Main { public static void main (String[]args) { int i,n = 33; boolean isprime= true; // 0 and 1 are not prime numbers also, negative numbers are not prime if(n < 2) { isprime = false; } else { // running loop till n is wasteful because for any number n the numbers in // the range(n/2 + 1, n) won't be divisible anyways. for(i=2; i <= n/2; i++) { if(n % i == 0) { isprime = false; break; } } } String result = isprime ? "Prime" : "not Prime"; System.out.println ("The number " + n + " is : " + result); // Time Complexity : O(N) // Space Complexity : O(1) // This program is better than previous version as : // Loops runs b/w [2, n/2] rather than [2, n-1] } }

### Output

33 is : Not Prime

**Method 4:** Optimization by √n

### Working

In this method we’ll use for loop to iterate from 2 to square root of the number as it’s known that all the factors of the number lay in the interval [2, sqrt(number)].

For an integer input number, we check,

- If the number is lesser than 2.
- If the number has factors other than 1 and the number itself in the interval [2, sqrt(number)].
- If either of the conditions are satisfied, the number is not a Prime.

### Java Code

public class Main { public static void main (String[]args) { int i,n = 29; boolean isprime= true; // 0 and 1 are not prime numbers also, negative numbers are not prime if(n < 2) { isprime = false; } else { // If a number n is not a prime, it can be factored into two factors a and b: // n = a * b /*Now a and b can't be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So in any factorization of n, at least one of the factors must be smaller than the square root of n, and if we can't find any factors less than or equal to the square root, n must be a prime.*/ for(i=2; i <= Math.sqrt(n); i++) { if(n % i == 0) { isprime = false; break; } } } String result = isprime ? "Prime" : "not Prime"; System.out.println ("The number " + n + " is : " + result); // Time Complexity : O(N) // Space Complexity : O(1) // This program is better than previous version as : // Loops runs b/w [2, bn] rather than [2, n/2] } }

### Output

29 is : Prime

**Method 5:** Optimization by skipping even iteration

### Working

In this method we’ll use the for loop to iterate through the number in the given range [3, sqrt(number)] with a step of +1. We all know that an even number can’t be a prime and the only even prime is 2. Therefore we’ll run the loop with step 1 which will skip all the even numbers.

For a given integer input we check,

- If the number is lesser than 2.
- If the number has any factors other than 1 and the number itself in the given range of [3, sqrt(number)].
- We skip one iteration until the last element in reached.
- If either of the above conditions are satisfied, then the number is not a Prime.

### Java Code

public class Main { public static void main (String[]args) { int n = 29; if (isPrime (n)) System.out.println (n + " is a Prime Number"); else System.out.println (n + " is not a Prime Number"); } static Boolean isPrime (int n) { // 0 and 1 are not prime numbers // negative numbers are not prime if (n <= 1) return false; // special case as 2 is the only even number that is prime else if (n == 2) return true; // Check if n is a multiple of 2 thus all these won't be prime else if (n % 2 == 0) return false; // If not, then just check the odds for (int i = 3; i <= Math.sqrt (n); i += 2) { if (n % i == 0) return false; } return true; } }

### Output

29 is : Prime

**Method 6:** Basic Recursion technique

### Working

In this method we’ll use recursion to recursively iterate through each number and check whether it’s a factor of the number of not. To learn more about recursion in java, check out Recursion .

For a given integer input,

- Define a recursive function with base case as follows
- If number == iter, return True.
- If number%iter == 0, return False.
- If a number<2, return False.

- Set recursive step call as checkPrime(number, iter+1).

### Java Code

public class Main { public static void main (String[]args) { int i = 2; boolean isprime= true; int n = 37; isprime=checkPrime(n, i); String result = isprime ? "Prime":"not Prime"; System.out.println(n + " is : "+ result); } static Boolean checkPrime(int n, int i) { // 0, 1 and negative numbers are not prime if (n < 2) return false; // if this satisfies then its prime as we // have completed recursion from 2 to n if (i == n) return true; // Base cases if (n % i == 0) return false; i += 1; return checkPrime(n, i); } }

### Output

37 is : Prime

### Prime Course Trailer

### Related Banners

Get PrepInsta Prime & get Access to all 150+ courses offered by PrepInsta in One Subscription

C | C++ | Java | Python**Positive or Negative number:**C | C++ | Java | Python**Even or Odd number:****Sum of First N Natural numbers: C | C++ | Java | Python****Sum of N natural numbers: C | C++ | Java | Python****Sum of numbers in a given range: C | C++ | Java | Python****Greatest of two numbers: C | C++ | Java | Python****Greatest of the Three numbers: C | C++ | Java | Python****Leap year or not: C | C++ | Java | Python****Prime number: C | C++ | Java | Python****Prime number within a given range: C | C++ | Java | Python****Sum of digits of a number: C | C++ | Java | Python****Reverse of a number : C | C++ | Java | Python****Palindrome number: C | C++ | Java | Python****Armstrong number : C | C++ | Java | Python****Armstrong number in a given range : C | C++ | Java | Python****Fibonacci Series upto***nth*term : C | C++ | Java | Python**Find the***Nth*Term of the Fibonacci Series :**C | C++ | Java | Python****Factorial of a number : C | C++ | Java | Python****Power of a number : C | C++ | Java | Python****Factor of a number : C | C++ | Java | Python****Strong number : C | C++ | Java | Python****Perfect number : C | C++ | Java | Python****Automorphic number : C | C++ | Java | Python****Harshad number : C | C++ | Java | Python****Abundant number : C| C++ | Java | Python****Friendly pair : C | C++ | Java | Python**

public class Main {

public static void main(String[] args) {

int num = 22;

boolean flag = false;

for(int i = 2; i <= num/2; ++i)

{

if(num % i == 0)

{

flag = true;

break;

}

}

if (!flag)

System.out.println(num + " is a prime number.");

else

System.out.println(num + " is not a prime number.");

}

}