To check Prime Number In Java

Yuvaraj
6 min readAug 9, 2024

--

Basic Java Program

A prime number is a positive integer greater than 1 that has no divisors other than 1 and itself. In other words, a prime number can only be divided evenly (without leaving a remainder) by 1 and by the number itself.

Key Points:

  • Divisors: A divisor is a number that divides another number completely, without leaving a remainder.
  • Greater than 1: The number must be greater than 1. The number 1 is not considered a prime number.
  • Exactly Two Divisors: A prime number has exactly two distinct divisors: 1 and itself.

Examples of Prime Numbers:

  • 2: The only divisors of 2 are 1 and 2. (2 ÷ 1 = 2, 2 ÷ 2 = 1). So, 2 is a prime number.
  • 3: The only divisors of 3 are 1 and 3. (3 ÷ 1 = 3, 3 ÷ 3 = 1). So, 3 is a prime number.
  • 5: The only divisors of 5 are 1 and 5. (5 ÷ 1 = 5, 5 ÷ 5 = 1). So, 5 is a prime number.
  • 7: The only divisors of 7 are 1 and 7. (7 ÷ 1 = 7, 7 ÷ 7 = 1). So, 7 is a prime number.

The Prime Numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29….

Non-Examples (Not Prime Numbers):

  • 4: The divisors of 4 are 1, 2, and 4. Since it has more than two divisors, it’s not a prime number.
  • 6: The divisors of 6 are 1, 2, 3, and 6. Since it has more than two divisors, it’s not a prime number.
  • 9: The divisors of 9 are 1, 3, and 9. Since it has more than two divisors, it’s not a prime number.

Why Prime Numbers are Important:

  • Building Blocks: Prime numbers are like the “building blocks” of all natural numbers. Any number can be expressed as a product of prime numbers (this is called its prime factorization).
  • Security: Prime numbers play a crucial role in cryptography, especially in algorithms used for securing online communications.

Thus, a prime number is a number that can only be divided by 1 and itself, making it special and fundamental in mathematics.

import java.util.Scanner;

public class PrimeNumberChecker {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

// Input a number from the user
System.out.print("Enter a number: ");
int number = scanner.nextInt();

// Check if the number is prime
if (isPrime(number)) {
System.out.println(number + " is a prime number.");
} else {
System.out.println(number + " is not a prime number.");
}

scanner.close();
}

// Method to check if a number is prime
public static boolean isPrime(int num) {
// Handle edge cases for numbers less than 2
if (num <= 1) {
return false;
}

// Check for divisibility up to the square root of the number
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false; // If divisible, not a prime number
}
}

return true; // If not divisible by any number, it's a prime number
}
}

// Output:
/* Enter a number:
3
3 is a prime number. */

Explanation

  1. Input:
  • The program prompts the user to input a number.

2. Prime Check:

  • The isPrime method checks if the number is a prime number.
  • It handles edge cases where the number is less than or equal to 1, which are not prime numbers.
  • The method then checks divisibility by all numbers from 2 up to the square root of the input number (Math.sqrt(num)).
  • If the number is divisible by any of these, it’s not a prime number, and the method returns false.
  • If the number is not divisible by any of these, it’s a prime number, and the method returns true.

3. Output:

  • Based on the result from isPrime, the program prints whether the input number is a prime number or not.

Let’s break down the isPrime method:

public static boolean isPrime(int num) {
  • Purpose: This method checks whether the integer num is a prime number.
  • Return Type: boolean. It returns true if num is a prime number and false otherwise.

Edge Case Handling

if (num <= 1) {
return false;
}

Explanation: Prime numbers are defined as numbers greater than 1. If num is less than or equal to 1, it cannot be a prime number, so the method returns false immediately for such cases.

Divisibility Check

for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false; // If divisible, not a prime number
}
}

The for loop in the code above is designed to check if a number is a prime number by only iterating up to the square root of the number, which makes the process more efficient:

Explanation:

  1. Initialization:
for (int i = 2; i <= Math.sqrt(num); i++) {
  • int i = 2;: The loop starts with i initialized to 2. We start at 2 because 1 is a divisor for every number and does not help in determining primality (since prime numbers must be greater than 1).
  • i <= Math.sqrt(num);: The loop continues as long as i is less than or equal to the square root of num.

2. Checking Divisibility:

if (num % i == 0) {
return false; // If divisible, not a prime number
}
  • num % i == 0: This checks if num is divisible by i without leaving a remainder. If num % i equals 0, it means i is a divisor of num.
  • return false;: If num is divisible by any number i between 2 and Math.sqrt(num), it means num is not a prime number (since it has a divisor other than 1 and itself), and the method returns false.

Return True

return true;
  • After the Loop: If the loop completes and num was not found to be divisible by any number from 2 to num / 2, it means num is not divisible by any number other than 1 and itself. Hence, num is a prime number, and the method returns true.

In Short,

  • The loop checks for divisibility from 2 up to the square root of num.
  • If num is divisible by any i in this range, it is not a prime number, and the method returns false.
  • If no divisors are found in this range, the number is a prime number, as it was not divisible by any number other than 1 and itself.
  • Efficiency: By checking up to Math.sqrt(num), the loop reduces the number of iterations required to determine if num is a prime number. This is because any factor larger than Math.sqrt(num) would have a corresponding factor smaller than Math.sqrt(num). This optimization significantly speeds up the primality test, especially for larger numbers.

This method is more efficient than checking up to num / 2 because it reduces the number of divisibility checks required.

Method 2

import java.util.Scanner;

public class PrimeNumber {

public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number: ");
int number = sc.nextInt();

if(isPrime(number)) {
System.out.println(number + " is a prime number.");
} else {
System.out.println(number + " is not a prime number.");
}

sc.close();
}

public static boolean isPrime(int num) {
// Handle edge cases
if (num <= 1) {
return false;
}

// Check for divisibility from 2 up to num/2
for(int i = 2; i <= num / 2; i++) {
if(num % i == 0) {
return false; // num is divisible by i, so it's not a prime number
}
}

return true; // num is not divisible by any number other than 1 and itself
}
}

Divisibility Check

for(int i = 2; i <= num / 2; i++) {
if(num % i == 0) {
return false;
}
}

Loop: This for loop checks potential divisors from 2 up to num / 2.

  • Why up to num / 2? Checking divisibility beyond num / 2 is unnecessary because if a number num has a divisor larger than num / 2, the other corresponding divisor would be smaller than 2, which we would have already checked.

Condition Inside the Loop:

  • if(num % i == 0): This checks if num is divisible by i without leaving a remainder. The % operator returns the remainder of the division.
  • If num is divisible by i: This means num is not a prime number because it has a divisor other than 1 and itself. So, the method returns false.

Return True

return true;
  • After the Loop: If the loop completes and num was not found to be divisible by any number from 2 to num / 2, it means num is not divisible by any number other than 1 and itself. Hence, num is a prime number, and the method returns true.

In Short,

  1. Handle Edge Cases: Return false if num is less than or equal to 1.
  2. Check for Divisibility: Use a loop to test all possible divisors from 2 up to num / 2.
  • If any divisor divides num evenly, return false.
  • If no divisors are found, return true.

This method efficiently determines if a number is prime by checking divisibility only up to half of the number, optimizing performance.

--

--

Yuvaraj
Yuvaraj

No responses yet