How to generate the first n prime in Java

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 is divisible only by 1 and itself, and has no other factors.

For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on, are prime numbers because they cannot be divided evenly by any other numbers except 1 and themselves.

On the other hand, numbers such as 4, 6, 8, 9, 10, 12, and 14 are not prime numbers because they have divisors other than 1 and themselves. For example, 4 can be divided evenly by 2, and 9 can be divided evenly by 3.

Prime numbers have numerous applications in mathematics and computer science, including cryptography, number theory, and prime factorization.

Algorithm

The algorithm performs the below-mentioned steps to check if a number is prime or not:

If the number is less than or equal to 1, it is not a prime number. Return false.
If the number is equal to 2, it is a prime number. Return true.
If the number is even (divisible by 2), it is not a prime number. Return false.
Perform a loop starting from 3 and incrementing by 2 until reaching the square root of the number.
- Check if the number is divisible by the current iteration value.
  - If it is divisible, the number is not a prime number. Return false.
  - If it is not divisible, continue to the next iteration.
If the loop completes without finding any divisors, the number is a prime number. Return true.

The below code implements the algorithm given above.

Code

import java.util.ArrayList;
import java.util.List;
class PrimeGenerator {
    public static List<Integer> generatePrimes(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        int num = 2; // Start checking for primes from 2
        while (primes.size() < n) {
            if (isPrime(num)) {
                primes.add(num);
            }
            num++;
        }
        return primes;
    }
    public static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        // Check for divisibility by odd numbers from 3 up to the square root of num
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int n = 100; // Change this value to generate a different number of primes
        List<Integer> primes = generatePrimes(n);
        System.out.println("First " + n + " prime numbers:");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

Prime number generation

Code explanation

Here is the line-by-line explanation of the code given above:

Lines 21–23: Checks if num is less than or equal to 1, in which case it returns false since prime numbers are greater than 1.

Lines 24–26: Checks if num is equal to 2, which is a special case because 2 is the only even prime number. If num is 2, return true.

Lines 27–29: Checks if num is divisible by 2. If it is divisible evenly, it means num is an even number other than 2, and, therefore, not a prime number. In that case, return false.

Lines 32–36: If none of the above conditions are met, the method enters a for loop that starts from 3 and iterates up to the square root of num. It increments i by 2 in each iteration, checking only odd numbers since even numbers greater than 2 cannot be prime. Within the loop, check if num is divisible by i. If it is divisible evenly, it means num has a factor other than 1 and itself, so return false.

Line 38: If none of the conditions in the loop are met, it means num is not divisible by any odd numbers up to its square root. Thus, it is a prime number, and the method returns true.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources