Back to: Java Tutorials
Prime numbers are integers that are only divisible by 1 and themselves. In other words, a prime number cannot be divided evenly by any other number except 1 and itself. In this tutorial, we will write a Java program to determine if a given number is prime or not.
Step 1: Understanding the logic
To determine if a number is a prime, we can use a simple algorithm that checks if the number is divisible by any number between 2 and the square root of the number. If the number is divisible by any of these numbers, then it is not prime. Otherwise, it is prime.
Step 2: Writing the Java code
Let’s start by writing a Java function that checks if a given number is prime or not.
public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
This function takes an integer as input and returns true if the number is prime and false if it is not.
Here’s how the function works:
- First, we check if the number is less than or equal to 1. If it is, then it is not prime, so we return false.
- Next, we loop through all numbers between 2 and the square root of the number. For each number, we check if the number is divisible by that number. If it is, then it is not prime, so we return false.
- If we have looped through all numbers and none of them divide the number evenly, then the number is prime, so we return true.
Step 3: Testing the code
Now that we have written the isPrime function, let’s test it with some sample inputs.
public static void main(String[] args) {
int num1 = 7;
int num2 = 12;
if (isPrime(num1)) {
System.out.println(num1 + " is a prime number");
} else {
System.out.println(num1 + " is not a prime number");
}
if (isPrime(num2)) {
System.out.println(num2 + " is a prime number");
} else {
System.out.println(num2 + " is not a prime number");
}
}
This code tests the isPrime function with two numbers, 7 and 12. The output of this program should be:
7 is a prime number
12 is not a prime number
Step 4: Optimizing the code
The isPrime function works correctly, but it can be optimized further. One optimization we can make is to check if the number is even before looping through all odd numbers between 3 and the square root of the number. If the number is even and not 2, then it is not prime.
Here is the optimized version of the isPrime
function:
public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
if (n == 2 || n == 3) {
return true;
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
Here is how this optimized version works:
if (n <= 1) { return false; }
: This line checks if the input numbern
is less than or equal to 1. Ifn
is less than or equal to 1, the function returnsfalse
because 1 and all numbers less than 1 are not considered prime.if (n == 2 || n == 3) { return true; }
: This line checks if the input numbern
is equal to 2 or 3. Ifn
is equal to 2 or 3, the function returnstrue
because 2 and 3 are the only two prime numbers that are less than or equal to 3.if (n % 2 == 0 || n % 3 == 0) { return false; }
: This line checks if the input numbern
is divisible by 2 or 3. Ifn
is divisible by 2 or 3, the function returnsfalse
because all even numbers (except 2) and all numbers divisible by 3 are not considered prime.for (int i = 5; i * i <= n; i += 6) {
: This line starts afor
loop that checks only prime numbers in the form of 6k+1 and 6k-1 less than or equal to the square root ofn
. The loop incrementsi
by 6 in each iteration because all other numbers that are not in the form of 6k+1 or 6k-1 can be represented as the product of these prime numbers.if (n % i == 0 || n % (i + 2) == 0) { return false; }
: This line checks ifn
is divisible by eitheri
ori+2
. Ifn
is divisible by either of these two prime numbers, the function returnsfalse
becausen
is not a prime number.return true;
: If none of the previous conditions have returnedfalse
, the function returnstrue
becausen
is a prime number.
Also, see the example code JavaExamples_NoteArena in our GitHub repository. See complete examples in our GitHub repositories.
Follow us on social media
Follow Author