In this article, we will discuss the problem of identifying a prime number program in Java. We will discuss the definition and meaning of prime numbers, 3 different ways to identify a prime number in Java, all prime numbers between 2 numbers, etc. So, let’s get started with the definition of prime numbers.
What are Prime Numbers in Java?
Prime numbers are natural numbers that are divisible by only 1 and the number itself. For instance, 7 is a prime number because its only 2 factors are 1 and 7 itself. However, 6 is not a prime number because apart from 1 and 6, there are other factors of 6 and they are 2 and 3.
Some examples of prime numbers in Java are 3,5,7,11,13,17,19,23, etc.
The numbers that are not prime are called composite numbers. However, in mathematics, 1 is considered as neither prime nor composite.
Smallest Prime Number in java
The smallest prime number is 2. This is because 1 is neither prime nor composite. After 1, 2 is the first number that is divisible by 1 and 2 itself only. So, 2 is the smallest prime number.
Facts about Prime Numbers in Java
Let us now look at some of the interesting facts about prime numbers that may come in handy.
- 2 is the only even prime number. This is because all the other even numbers will be divisible by 2 also apart from 1 and the number itself.
- 2 and 3 are the only consecutive prime numbers. No such pair exists later.
- The number 5 is the only prime number that ends with 5. After this, any number ending with 5 will not be a prime number as it will be divisible by 5 also.
- After 2 and 3, every prime number is either of form 6n+1 or 6n-1.
So, now that we have enough knowledge of prime numbers, let us now move to the prime number program in Java.
Prime Number Program in Java
So, the problem statement is very simple. We are given a number and we have to determine whether this number is a prime number or not. For instance, if we are given 7, we will print “YES” else if we are given 10, we will print “NO”.
So, let us understand the process in detail.
Method 1: Complete Factorization Prime Number Program in Java
So, we know that the prime numbers are the numbers that are only divisible by 1 and the number itself. Also, we know that every number is divisible by 1 and itself. So, don’t have to check that.
So, this is the negation method. This means that instead of checking or proving that the number is prime, we will; try to prove that the number is non-prime (composite or 1). If we fail to prove the number non-prime, it will automatically be a prime number.
So, we can follow the following algorithm
Algorithm to Check Prime Number in Java
- Check if the input number (N) is 1. If it is 1, it is neither prime nor composite. Still, it is not prime so we will print “NO”
- Else, iterate from 2 to N-1 and check if any number is able to divide the number N completely i.e. if any number from 2 to N-1 is a factor of N. If we find even one number that is a factor of N, N will not be a prime number as we would have a number apart from 1 and N that divides N completely. So, in this case, also, print “NO”
- Finally, if we have iterated from 2 to N-1 and have not found any factor of N, this means that N is only divisible by 1 and N itself. So, it is a prime number. Hence, print “YES”
Now that we have understood this procedure, let us write the code for the same.
Program for Complete Prime Factorization for finding Prime Number in Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
if(n == 1) {
System.out.println("NO");
return;
}
for(int i=2;i<n;i++) {
if(n % i == 0) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
}
Time Complexity of prime number in java: The time complexity of this method is O(N) as we are traversing almost N numbers in case the number is prime.
Space Complexity (Auxiliary Space) of prime number in Java: Since we have not used any extra space, the auxiliary space is O(1).
Method 2: Half Factorization Prime Number Program in Java
So, we saw that we can simply iterate from 2 to N-1 to identify whether the number given to us is prime or not. However, if there is a large number given to us as input, this method is not that optimized.
If we think carefully, we can understand that we don’t need to check till N-1. Obviously, N-1 can never divide N. So, what should be the endpoint?
Well, if a number is even, it gets divided by 2. So, its half will also be its factor. Also, if a number is odd, we can’t say that its half will be its factor. However, there will be at least 1 factor before its half also.
So, we can say that we can check if a number is prime or not by iterating from 2 to N/2. If there exists a factor between 2 to N/2, the number will be non-prime, else it will be prime.
So, let us now write the code for this method.
Code for Half Factorization to identify a Prime Number in Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
if(n == 1) {
System.out.println("NO");
return;
}
for(int i=2;i<=n/2;i++) {
if(n % i == 0) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
}
Time Complexity of prime number in java: Well, the time complexity remains the same i.e. O(N). However, we are iterating approximately just half as compared to before since we are going till N/2.
Space Complexity (Auxiliary Space) of prime number in java: Since we have not used any extra space, the auxiliary space is O(1).
So, we have reduced the number of iterations to half in the above method. However, can we write a prime number program in Java with not just reduced iterations, but also reduced asymptotic time complexity. So, let us see that method.
Method 3: Square Root Method Prime Number Program in Java
We saw in the previous method, we were able to reduce the iterations to half. Still, the time complexity remains the same. The logic for reducing the iterations to half was mathematical.
Similarly, we also have another mathematical logic that will reduce the iterations and time complexity further. Let us 2 composite numbers. One of them should be a perfect square and the other should not be a perfect square. So, let’s say we have the two numbers 40 (not a perfect square) and 36 (perfect square). The factors of these numbers are shown below.
So, can you find anything specific in these 2 factorizations?
The image above shows that the upper half and lower half of factorizations are mirror images of each other.
In the case of perfect squares, the square root factor is in the middle and is not mirrored. However, the rest of the factors are mirrored.
What does this mean? This means that if the number is a composite number, whether it is a perfect square or not, there will be at least 1 factor on or before the square root of the number. This is because the factors below the square root are just mirrored images of the factors above the square root.
So, in order to check whether a number is a prime number or not, we check the factors of the number on or below the square root of the number. If there exists some factor, the number is non-prime, else it will be prime.
Now that we have understood the procedure, let us write the code for the same.
Program for Square Root Method to identify a Prime Number in Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
if(n == 1) {
System.out.println("NO");
return;
}
for(int i=2;i*i<=n;i++) {
if(n % i == 0) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
}
Time Complexity of prime number in java: The time complexity of this solution is root N i.e. O(√N). This is because we are traversing just √N numbers.
Space Complexity (Auxiliary Space) prime number in java: Since we have not used any extra space, the auxiliary space is O(1).
So, these are the three methods to identify whether a number is a prime number or not.
What would you do if we ask you to print the prime numbers in a range i.e. we give you 2 numbers, low and high and you have to print all the prime numbers between low and high. So, we can use the same method to identify a prime number as shown below and just apply a loop from low to high and if a prime number is detected, we print it. The code for the same is shown below.
Program to print Prime Numbers in a Range
import java.util.*;
public class Main {
public static boolean isPrime(int n) {
if(n == 1) return false;
for(int i=2;i*i<=n;i++) {
if(n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int low = scn.nextInt();
int high = scn.nextInt();
for(int i=low;i<=high;i++) {
if(isPrime(i)) System.out.println(i);
}
}
}
So, we hope that you liked the discussion and have understood the concepts in detail. We hope you understood all the 3 methods to identify a prime number. Keep learning and moving forward. Hope to see you again at PrepBytes.
Other Java Programs
Java Program to Add Two Numbers
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List