This article is part of my #100DaysOfCode and #100DaysOfBlogging challenge. R1D19

Today I am solving the Sieve of Eratosthenes side exercise of the Exercism PHP track.

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

My solution

The algorithm is straight forward. There are two exceptions to a default behavior.

  1. If the limit is less than 2, an empty array can be returned.
  2. When removing multiples of a prime from an array, make sure to not remove the prime itself.
<?php

declare(strict_types = 1);

function sieve(int $limit) : array
{
    if ($limit < 2) {
        return [];
    }

    $prime = 2;
    $range = range($prime, $limit);

    for (; $prime <= $limit; $prime++) {
        removeMultiplesFromRange($prime, $range);
    }

    return array_values($range);
}

function removeMultiplesFromRange(int $prime, array &$range) : void
{
    foreach ($range as $key => $value) {
        if ($prime === $value) {
            continue;
        }

        if (0 === $value % $prime) {
            unset($range[$key]);
        }
    }
}