Methods to Write Prime Number Program in Java
Now, let's discuss different methods to write the prime number program:
1. Brute Force Method: In the brute force method, we start a loop from 2 to the number itself (n). Inside the loop, we check if the number is divisible by any value between 2 and n-1. If it is divisible, we conclude that the number is not prime and break the loop. If the loop completes without finding any divisors, we declare the number as prime.
2. Optimized Method: The optimized method is an improvement over the brute force approach. Instead of checking divisibility up to n-1, we only need to check until the square root of n. This is because if a number is not prime, it must have at least one factor less than or equal to its square root. By reducing the range of divisors to check, we can significantly improve the efficiency of the program.
3. Using Built-in BigInteger Class: Java provides a built-in class called BigInteger that supports arbitrary-precision arithmetic. The BigInteger class has a method called isProbablePrime() that determines whether a given BigInteger is prime or not. This method uses the Miller-Rabin primality test, which is a probabilistic algorithm that efficiently determines the primality of large numbers. Using the BigInteger class simplifies the prime number program and handles large numbers efficiently.
4. Sieve of Eratosthenes: The Sieve of Eratosthenes is an ancient algorithm used to find all prime numbers up to a given limit. It works by creating a boolean array of size n+1 (where n is the limit) and initializing all elements to true. Then, it starts from 2 and marks all multiples of 2 as non-prime. It continues with the next unmarked number (which is always prime) and marks its multiples as non-prime. This process is repeated until all numbers up to the square root of n are checked. The remaining unmarked numbers are the prime numbers.
Let’s see the different algorithms for writing Prime Number Programs in Java.
Program to Check Prime Number using a for loop
Java program to check if a given number is prime using a for loop:
import java.util.Scanner;
class PrimeNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
if(isPrime(num)) {
System.out.println(num + " is a prime number");
} else {
System.out.println(num + " is not a prime number");
}
}
public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
You can also try this code with Online Java Compiler
Input
13
Output
13 is a prime number
Explanation
This Java program checks if a given number is prime. It prompts the user for input, then utilizes a `for` loop to iterate from 2 up to the square root of the number. Within each iteration, it checks if the number is divisible by the current value of `i`. If a divisor is found, it concludes the number is not prime. If no divisors are found, it's a prime number.
Program to Check Prime Number using a while loop
Java program to check if a given number is prime using a while loop:
Java
import java.util.Scanner;
class PrimeCheck {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
if(isPrime(num)) {
System.out.println(num + " is a prime number");
} else {
System.out.println(num + " is not a prime number");
}
}
public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
int i = 2;
while (i <= Math.sqrt(num)) {
if (num % i == 0) {
return false;
}
i++;
}
return true;
}
}
You can also try this code with Online Java Compiler
Input
17
Output
17 is a prime number
Explanation
This Java program checks if a given number is prime using a `while` loop. It starts by prompting the user for input. The `isPrime` method iterates from 2 up to the square root of the number using a `while` loop, checking for divisibility in each iteration. If a divisor is found, it concludes the number is not prime. If no divisors are found, it deems the number as prime.
Naive Approach for Writing Prime Number Program in Java
As per the definition, A number n is a prime number if there is no number b/w one and n that can divide n.
We are going to use this simple fact to write our program.
Java
public class PrimeNumber {
// function to check if a number is prime
private static boolean isPrime(int number){
// variable to store if the number is prime
boolean isNumberPrime = true;
/*
loop in the range [2,number-1] to check
if there is any integer that can divide
the number.
*/
for(int i=2; i<number; i++){
if( (number % i) == 0 ) {
isNumberPrime = false;
break;
}
}
return isNumberPrime;
}
public static void main(String[] args) {
// Defining two number 7 and 8
int number1 = 7;
int number2 = 8;
// checking if they are prime or not
boolean result1 = isPrime(number1);
boolean result2 = isPrime(number2);
// Printing the result
System.out.println(number1+" is "+((result1)? "a Prime number":" not a Prime number"));
System.out.println(number2+" is "+((result2)? "a Prime number":" not a Prime number"));
}
}
You can also try this code with Online Java Compiler
Output
7 is a Prime number
8 is not a Prime number
Explanation
We have made isPrime function to determine if a number is prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to number-1 to check if any number divides the “number”. If any integer exists between two and number-1 that divides the number, then the “number” is not a prime, and hence we assign isNumberPrime as false.
Time and Space Complexity
- Looping over the range [2, number-1] will take O(n) operations, and hence the time complexity is O(n).
- We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).
Optimised Approach to Write Prime Number Program in Java
Let’s see the factors of a number to find some pattern:
36 = (1,2,3,4),(6),(36,18,12,9).
We have kept factors of 36 in three groups. If we multiply a member of the first group by the respective member of the second group, we will get 36, i.e.
1*36 = 36, 2*18 = 36, 3*12 = 36, 4*9 = 36.
So, when we check that if 36 is divisible by the member of the first group, then we are not required to check the same by the second group. This led to the observation that we only need to check factors until sqrt(n) to determine whether it is prime.
Let’s verify the fact with another number, 12.
12 = (1,2,3),(12,6,4).
We have only two groups in this case because 12 is not a perfect square. Here also, multiplying the respective members of the first and second groups will result in 12. So, we only need to check factors until sqrt(12) ~ 3 to determine whether it is prime.
Code in Java
Java
public class PrimeNumber {
// function to check if a number is prime
private static boolean isPrime(int number){
// variable to store if the number is prime
boolean isNumberPrime = true;
/*
loop in the range [2,sqrt(n)] to check
if there is any odd integer that can divide
the number.
*/
for(int i = 2; i * i <= number; i++ ){
if( (number % i) == 0 ) {
isNumberPrime = false;
break;
}
}
return isNumberPrime;
}
public static void main(String[] args) {
// Defining two number 49456 and 123677
int number1 = 49456;
int number2 = 123677;
// checking if they are prime or not
boolean result1 = isPrime(number1);
boolean result2 = isPrime(number2);
// Printing the result
System.out.println(number1+" is "+((result1)? "a Prime number": "not a Prime number"));
System.out.println(number2+" is "+((result2)? "a Prime number": "not a Prime number"));
}
}
You can also try this code with Online Java Compiler
Output
49456 is not a Prime number
123677 is a Prime number
Explanation
We have made isPrime function to determine if a number is a prime. This function takes a number (an integer) as its parameter. Then we loop on the range two to sqrt(n) to check if any integer exists that divides the number, then the “number” is not a prime, and hence we assign isNumberPrime as false. We are using the expression i * i <= number to stop the execution of the loop when the integer lies outside the mentioned range.
Time and Space Complexity
- Looping over the range [2, sqrt(n)] will take O(sqrt(n)) operations, and hence the time complexity is O(sqrt(n)).
- We are not using any extra space except for variables like isNumberPrime; hence, the space complexity is O(1).
Frequently Asked Questions
How do you write a prime number program in Java?
In Java, write a program that iterates through numbers, checking for factors up to their square root. If a number has no factors other than 1 and itself, it's prime.
What is the method to find a prime number in Java?
The method involves iterating from 2 to the square root of the number and checking for divisibility. If the number is only divisible by 1 and itself, it's prime.
What are the first 10 prime numbers print?
The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. These are natural numbers greater than 1 that have no divisors other than 1 and themselves.
What is the logic of a prime number?
A prime number is one that's only divisible by 1 and itself. To determine if a number is prime, iterate from 2 to its square root. If it's divisible by any number in this range, it's not prime; otherwise, it is.
Conclusion
In conclusion, we can say that prime number program in java are very important in computer science. They have diverse applications. We can find if a number is prime using various approaches. In this article, we improved approach by approach, and, finally, the most optimised algorithm has taken O(sqrt(n)) operations to determine if a number is prime.
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.
Happy Learning!
8+ registered 