Previous
Written by: rJTutorial Team | Last Updated:

Java Program To Find Prime Numbers

Calculating prime numbers is a fundamental exercise for every Java developer. Not only does it help you practice loop structures and conditional logic, but it also introduces you to algorithmic optimization. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself (e.g., 2, 3, 5, 7, 11...).

In real-world software engineering, prime numbers play a massive role in Cryptography (like RSA encryption) and Hashing algorithms. Understanding how to efficiently identify them is a valuable skill.

Here's a clean, efficient Java program to find all prime numbers up to a specified limit:

public class PrimeNumbers {
    public static void main(String[] args) {
        int limit = 100; // The upper bound for our search
        System.out.println("Prime numbers up to " + limit + ":");

        // We start the loop at 2, as 0 and 1 are not prime numbers
        for (int i = 2; i <= limit; i++) {
            boolean isPrime = true;

            /* 
               Check if 'i' is divisible by any number from 2 up to its square root.
               We use Math.sqrt(i) for efficiency.
            */
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false; // Found a divisor, so it's not prime
                    break;           // Exit the inner loop immediately
                }
            }

            // If no divisors were found, i is prime
            if (isPrime) {
                System.out.print(i + " ");
            }
        }
    }
}
Developer Tip: The use of Math.sqrt(i) is a classic optimization. If a number n has a factor larger than its square root, it must also have a corresponding factor smaller than its square root. Checking beyond the square root is redundant and slows down your code.

How the Logic Works

The program uses a nested loop structure to filter out non-prime numbers:

  • The Outer Loop: This iterates through every integer starting from 2 up to your defined limit.
  • The Inner Loop: For every number (i), we test if it can be divided evenly by any number (j).
  • The Modulo Operator (%): This is the secret sauce. i % j == 0 checks if the remainder is zero. If it is, i is a composite number, and we flag isPrime as false.
Common Mistake: Many beginners start their loops at 0 or 1. Remember that by mathematical definition, prime numbers must be greater than 1. Starting your loop at 2 avoids logic errors and unnecessary checks.
Best Practice: In a professional production environment, you should move the prime-checking logic into its own method, such as public static boolean isPrime(int n). This makes your code modular, easier to test, and reusable across different parts of your application.

This program iterates through numbers from 2 to the specified limit. For each number, it checks if it is divisible by any number from 2 to its square root. If it is not divisible by any of these numbers, then it is considered a prime number and printed.

Watch Out: While this "Trial Division" method works great for small limits (like 100 or 1,000), it becomes very slow for extremely large numbers. If you need to find primes in the millions or billions, look into more advanced algorithms like the Sieve of Eratosthenes.

Real-World Example: ID Generation

Imagine you are building a system that needs to distribute tasks across different servers. Some developers use prime numbers to determine "sharding" logic or to ensure that unique IDs generated by different services don't collide easily when using modular arithmetic. Understanding the distribution of primes helps in creating more balanced systems.

Previous