How Efficient is the Sieve of Eratosthenes for Prime Number Generation?

Most Elegant Prime Number Generation: A Sieve Approach

When faced with the challenge of generating prime numbers, striving for elegance in code is a noble pursuit. While many methods exist for finding primes, the Sieve of Eratosthenes stands out for its simplicity and efficiency.

The Sieve of Eratosthenes operates by creating a boolean array of length n, which represents the numbers from 1 to n. The array is initially set to true for all elements, indicating that each number is a potential prime. The algorithm then iterates through the array, starting at the first unmarked number, which is 2. It marks all multiples of 2 as non-prime by setting their values in the array to false. It then moves to the next unmarked number, 3, and repeats the process, marking all multiples of 3 as non-prime. This continues until the last unmarked number, √(n).

By using this approach, the Sieve of Eratosthenes significantly reduces the number of checks required to find primes, offering a highly efficient solution. Consider the following Java implementation of the Sieve:

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

This code creates a BitSet to represent the numbers from 1 to n and sets all elements initially to true. It then iterates through the array, marking all multiples of each prime number (starting with 2) as non-prime. The result is a BitSet where the only elements set to true represent the prime numbers.

The above is the detailed content of How Efficient is the Sieve of Eratosthenes for Prime Number Generation?. For more information, please follow other related articles on the PHP Chinese website!