Efficient Prime Number Sieve in PHP - Detailed Explanation of the Sieve of Eratosthenes

Overview

A prime number is a natural number greater than 1 that is only divisible by 1 and itself. Finding prime numbers is a common task in programming. This article introduces a classic and efficient method to find primes—the Sieve of Eratosthenes. This algorithm quickly identifies all primes within a given range by marking primes and their multiples.

Principle of the Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple yet effective ancient algorithm. The core idea is:

Create a boolean array of length n+1, initialized to true;

Start from 2, mark the multiples of each prime as false;

Remaining true values represent prime numbers.

PHP Implementation Example

The following sample code demonstrates how to implement the sieve in PHP:

function sieveOfEratosthenes($n) {
    // Create a boolean array of length n+1 initialized to true
    $isPrime = array_fill(2, $n - 1, true);
    
    // Mark multiples of primes as false starting from 2
    for ($i = 2; $i * $i <= $n; $i++) {
        if ($isPrime[$i]) {
            for ($j = $i * $i; $j <= $n; $j += $i) {
                $isPrime[$j] = false;
            }
        }
    }
    
    // Collect all indices that remain true, these are primes
    $primes = [];
    foreach ($isPrime as $number => $is) {
        if ($is) {
            $primes[] = $number;
        }
    }
    return $primes;
}

$range = 100;
$primes = sieveOfEratosthenes($range);

// Output primes
foreach ($primes as $prime) {
    echo $prime . " ";
}

This code creates a boolean array of size n+1 with all values set to true, then uses nested loops to mark multiples of primes as false. Finally, all indices still marked true are collected as primes.

Example Output

Running the above code for the range 100 outputs the following primes:

<span class="fun">2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 </span>

This confirms the algorithm accurately and efficiently finds all primes within the specified range.

Performance Analysis

The time complexity of the Sieve of Eratosthenes is approximately O(n log log n), making it suitable for quickly finding primes in small to moderate ranges. It significantly improves performance by eliminating multiples of primes rather than checking each number individually.

Conclusion

This article presented the PHP implementation of the Sieve of Eratosthenes, a simple and efficient algorithm for prime number identification. Understanding this method helps solve programming problems involving primes with improved efficiency and performance.