What's the Most Elegant Way to Generate a List of Prime Numbers?

Elegant way to generate prime numbers

This article explores how to generate a list of prime numbers in the most elegant way. An elegant algorithm should be clear, concise and efficient.

Improved Sieve of Eratosthenes

One method is to improve the sieve of Eratosthenes. The following is an elegant Java implementation:

public static ArrayList<Integer> generatePrimes(int n) {
    ArrayList<Integer> primes = new ArrayList<>();
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

This algorithm efficiently identifies prime numbers less than or equal to n by iteratively removing multiples of the found prime numbers, ensuring accuracy and efficiency.

Other elegant solutions

In addition to the improved sieving method, the following methods can also be considered:

• LINQ-based generation: Use the lazy loading feature of LINQ to elegantly generate prime number sequences. (This part requires specific code examples to be clearer)
• BigInteger method: Using Java's BigInteger class and nextProbablePrime method can achieve concise and efficient code. (This part requires specific code examples to be clearer)
• Prime number data source: Read directly from pre-generated prime number files or databases, fast and reliable.

Choose the most appropriate approach to building elegant prime number generation algorithms based on your specific needs and preferences for efficiency, simplicity, and readability.

The above is the detailed content of What's the Most Elegant Way to Generate a List of Prime Numbers?. For more information, please follow other related articles on the PHP Chinese website!