What's the Most Elegant Method for Generating the First N Prime Numbers?

An elegant way to generate prime numbers

The goal is to write a function generatePrimes(n) that returns the first n prime numbers. There are multiple ways to achieve this functionality, each with their own pros and cons. This article explores the most elegant methods.

The original approach usually uses nested loops to check prime numbers. While this approach works, it lacks elegance due to its repetitive and nested structure. A more elegant approach is to use the Sieve of Eratosthenes, which has a time complexity of O(n log log n).

The Sieve of Eratosthenes works by creating a boolean array of size n, with all elements initially set to true. Array indexes represent numbers from 0 to n-1. The algorithm first sets the elements at index 0 and 1 to false since they are not prime numbers. Then, for each index i, it sets all multiples of i in the array to false. This process is repeated for all indices up to the square root of n. The remaining true elements in the array represent prime numbers.

Here is an elegant Java implementation of the Sieve of Eratosthenes:

<code class="language-java">public static List<Integer> generatePrimes(int n) {
    if (n <= 0) {
        return new ArrayList<>();
    }
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}</code>

This code efficiently and elegantly generates the first n prime numbers using the sieve of Eratosthenes. The time complexity is O(n log log n), the code is concise and clear, and it is ideal for generating prime numbers.

The above is the detailed content of What's the Most Elegant Method for Generating the First N Prime Numbers?. For more information, please follow other related articles on the PHP Chinese website!