Prime Number Or Not In Java Using For Loop

This article will guide you through determining if a given number is prime using a for loop in Java. You will learn the definition of a prime number and how to implement a simple algorithm to check for primality.

Problem Statement

Identifying whether a number is prime is a fundamental problem in computer science and mathematics. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Efficiently checking for primality is crucial in various applications, including cryptography and number theory.

Example

If we input the number 7, the program should output:

7 is a prime number.

If we input the number 10, the program should output:

10 is not a prime number.

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• Java syntax: Variables, data types, conditional statements (if-else), and loops (for).
• Arithmetic operators: Modulo operator (%).
• Input/Output: Reading user input using Scanner.

Use Cases or Case Studies

• Cryptography: Prime numbers are the foundation of many encryption algorithms, such as RSA, where large prime numbers are used to generate public and private keys.
• Hashing: Some hashing functions use prime numbers to distribute data evenly across hash tables, reducing collisions.
• Random number generation: Prime numbers can be used in algorithms to generate pseudo-random numbers.
• Number theory research: Primality testing is a core operation in various number theory problems and research.
• Educational tools: Teaching fundamental programming concepts and mathematical definitions.

Solution Approaches

We will focus on a straightforward approach using a for loop to check for divisors.

Approach 1: Basic for loop check

This approach iterates from 2 up to the number minus 1, checking for any divisors. If a divisor is found, the number is not prime.

• One-line summary: Iterate from 2 to n-1 and check for divisibility.

// Prime Number Check using For Loop
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Create a Scanner object to read user input
        Scanner scanner = new Scanner(System.in);

        // Step 2: Prompt the user to enter a number
        System.out.print("Enter a number: ");
        int number = scanner.nextInt();

        // Step 3: Initialize a boolean flag to track primality
        boolean isPrime = true;

        // Step 4: Handle special cases for numbers less than or equal to 1
        if (number <= 1) {
            isPrime = false;
        } else {
            // Step 5: Loop from 2 up to number - 1
            for (int i = 2; i < number; i++) {
                // Step 6: Check if the number is divisible by 'i'
                if (number % i == 0) {
                    isPrime = false; // If divisible, it's not prime
                    break;           // No need to check further
                }
            }
        }

        // Step 7: Print the result based on the isPrime flag
        if (isPrime) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }

        // Step 8: Close the scanner
        scanner.close();
    }
}

Run

• Sample output:

  Enter a number: 13
  13 is a prime number.

Enter a number: 9
    9 is not a prime number.

• Stepwise explanation:

1. Input: The program first takes an integer input from the user.
2. Initialization: A boolean variable isPrime is set to true by default, assuming the number is prime until proven otherwise.
3. Edge Cases: Numbers less than or equal to 1 are not prime, so these are handled immediately.
4. Looping for Divisors: A for loop starts from i = 2 and continues as long as i is less than the number. We start from 2 because 1 is a divisor of all numbers, and we are looking for other divisors.
5. Divisibility Check: Inside the loop, number % i == 0 checks if number is perfectly divisible by i.
6. Not Prime: If a divisor is found, isPrime is set to false, and the break statement exits the loop early because there's no need to check further.
7. Output: Finally, based on the value of isPrime, the program prints whether the entered number is prime or not.

Approach 2: Optimized for loop (up to square root)

This approach optimizes the previous one by realizing that if a number n has a divisor greater than its square root, it must also have a divisor smaller than its square root. Therefore, we only need to check for divisors up to the square root of the number.

• One-line summary: Iterate from 2 up to the square root of n and check for divisibility.

// Optimized Prime Number Check
import java.util.Scanner;

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

        boolean isPrime = true;

        if (number <= 1) {
            isPrime = false;
        } else {
            // Loop from 2 up to the square root of the number
            // We cast Math.sqrt(number) to int because loop counter is int
            for (int i = 2; i * i <= number; i++) { // Equivalent to i <= Math.sqrt(number)
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

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

        scanner.close();
    }
}

Run

• Sample output:

``` Enter a number: 29 29