Last Updated on May 16, 2023 by Prepbytes
We’ll talk about what prime numbers are, what they signify, how to detect them in Java in three distinct methods, all prime numbers between two numbers, etc. Therefore, let’s begin with a definition of prime numbers.
What are Prime Numbers in Java?
Natural numbers known as prime numbers may only be divided by one (1) and by the number itself. One prime example is 7, which has only the number 7 itself and the number 1 as components. However, 6 is not a prime number since it has additional components, 2 and 3, in addition to factors 1 and 6.
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);
}
}
}
Conclusion
Checking for prime numbers is a fundamental problem in mathematics and computer science. In Java, there are several ways to check if a number is prime, including using a brute force algorithm, the Sieve of Eratosthenes, or the Miller-Rabin test.
The brute force algorithm is simple and straightforward but can be slow for larger numbers. The Sieve of Eratosthenes is a more efficient method for finding prime numbers up to a certain limit. The Miller-Rabin test is a probabilistic algorithm that is faster than the brute force method for larger numbers.
It’s important to keep in mind that there are limitations to these methods, and they may not work for extremely large numbers. In such cases, more advanced algorithms and techniques may be required.
Frequently Asked Questions
Q1. How can I check if a number is prime in Java?
Ans. There are several ways to check if a number is prime in Java, including using a brute force algorithm, the Sieve of Eratosthenes, or the Miller-Rabin test.
Q2. What is the brute force method for checking prime numbers?
Ans. The brute force method involves iterating over all integers between 2 and the square root of the number being checked, and checking if any of them divide the number evenly.
Q3. What is the Sieve of Eratosthenes method for checking prime numbers?
Ans. The Sieve of Eratosthenes is a method for finding all prime numbers up to a certain limit. It involves creating a list of numbers from 2 to the limit, and then iteratively crossing out all multiples of each prime number.
Q4. What is the Miller-Rabin test for checking prime numbers?
Ans. The Miller-Rabin test is a probabilistic algorithm for determining if a number is prime. It involves choosing a number of random bases, and checking if each one passes a certain test.
Q5. Can I use the brute force method for checking very large numbers?
Ans. The brute force method can become very slow for large numbers, as it involves iterating over many potential divisors. In such cases, more advanced algorithms and techniques may be required.
Q6. Are there any libraries in Java that can check if a number is prime?
Ans. Yes, there are several libraries in Java that can check if a number is prime, including the Apache Commons Math library and the BigInteger class in the standard library.
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