Java Program to Find Prime Numbers

Introduction

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number is a number that cannot be formed by multiplying two smaller natural numbers. This guide will show you how to create a Java program that finds prime numbers within a specified range.

Problem Statement

Create a Java program that:

• Takes an integer input n from the user.
• Finds and displays all prime numbers less than or equal to n.

Example 1:

• Input: n = 10
• Output: Prime numbers: 2, 3, 5, 7

Example 2:

• Input: n = 20
• Output: Prime numbers: 2, 3, 5, 7, 11, 13, 17, 19

Solution Steps

1. Prompt for Input: Use the Scanner class to read an integer input n from the user.
2. Check Each Number for Primality: Create a method to determine if a number is prime by checking if it is divisible by any number other than 1 and itself.
3. Loop Through All Numbers Up to n: Use a loop to check each number up to n to see if it is prime.
4. Display the Prime Numbers: Print the prime numbers found.

Java Program

import java.util.Scanner;

/**
 * Java Program to Find Prime Numbers
 * Author: https://www.javaguides.net/
 */
public class PrimeNumbersFinder {

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

        // Step 1: Prompt the user for input
        System.out.print("Enter a number to find all prime numbers up to that number: ");
        int n = scanner.nextInt();

        // Step 2: Find and display prime numbers up to n
        System.out.print("Prime numbers: ");
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }

    // Step 3: Method to check if a number is prime
    public static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Explanation

Step 1: Prompt for Input

• The program prompts the user to enter a number n. This number will be the upper limit for finding prime numbers.

Step 2: Find and Display Prime Numbers

• The program iterates through all numbers from 2 to n. For each number, it checks if the number is prime by calling the isPrime method.

Step 3: Method to Check If a Number Is Prime

• The isPrime method determines if a number is prime by checking if it is divisible by any number other than 1 and itself. The loop in this method runs up to the square root of the number (Math.sqrt(number)) to improve efficiency.

Key Points:

• Prime Number: A number that has only two distinct positive divisors: 1 and itself.
• Efficiency: The isPrime method checks divisibility up to the square root of the number, which reduces the number of iterations and makes the program more efficient.

Output Examples

Example 1:

Enter a number to find all prime numbers up to that number: 10
Prime numbers: 2 3 5 7 

Example 2:

Enter a number to find all prime numbers up to that number: 20
Prime numbers: 2 3 5 7 11 13 17 19 

Conclusion

This Java program efficiently finds all prime numbers up to a specified number n. By using a method that checks for prime numbers and iterating through all numbers up to n, the program is both straightforward and efficient. This method is commonly used in various mathematical and computational applications where prime numbers are needed.