Programming Praxis: Sieve of Eratosthenes Algorithm in PHP

sieve-php

// initialize the static primes applied across all chunks
$primes = [2];

// initialize the length of the numbers to sequence
$position = 1;
$length = 15485863;
$chunk = 100000;
$sets = floor($length / $chunk);
$remainder = $length % $chunk;

// step through each step
for ( $set = 1; $set <= $sets; $set++ )
{
   // process this set's chunk
   $position = processChunk($position, $chunk);
}

// when there is a remainder to the chunks
if ( $remainder )
{
   // process the remainder chunk
   processChunk($position, $remainder);
}

/**
 * Process each set of chunk length.
 *
 * @param  int $position The starting position in length.
 * @param  int $set      The chunk length from the starting position.
 * @return void
 */
function processChunk($position, $chunk)
{
   // include the global primes reference
   global $primes;

   // initialize the divisor number
   $divisor = end($primes);

   // initialize the distance reference
   $distance = $position + $chunk - 1;

   // initialize the array number sequence
   $nums = array_fill($position, $chunk, true);

   // when primes have been aggregated
   if ( count($primes) > 1 )
   {
      // point to the largest number in this set
      end($nums);

      // initialize a reference to the largest number in this set
      $end = key($nums);

      // step through each existing prime
      foreach ( $primes as $prime )
      {
         // cease iteration, as applicable
         if ( $prime > $end / 2 ) break;

         // command line output
         echo sprintf("Filtering derived prime: %d", $prime);

         // step through the number sequence
         foreach ( $nums as $i => $isCandidate )
         {
            // when this number is not a prime number candidate
            if ( $i % $prime == 0 )
            {
               // remove this number from the set
               unset($nums[$i]);
            }
         }
      }
   }

   do
   {
      // step through each item in the distance
      for ( $i = $position + $divisor; $i <= $distance; $i++ )
      {
         // when this number is not a prime number candidate, as applicable
         if ( $i > $divisor && $i % $divisor == 0 )
         {
            // remove this number from the set
            unset($nums[$i]);
         }
      }

      // fetch the next divisor
      if (( $divisor = nextDivisor($nums, $divisor) ))
      {
         // command line output
         echo sprintf("Prime number: %d", $divisor);

         // append the current prime
         $primes[] = $divisor;
      }
   }
   // while there is a prime divisor available in this set
   while ( $divisor );

   // aggregate the position
   return $position + $chunk;
}

/**
 * Fetch the next divisor from the set of numbers.
 *
 * @param  array $nums    The number array sequence reference.
 * @param  int   $divisor The current divisor.
 * @return int
 */
function nextDivisor(&$nums, $divisor)
{
   // step through the number sequence
   foreach ( $nums as $key => $isCandidate )
   {
      // when the current divisor is met
      if ( $key > $divisor )
      {
         // return the next divisor
         return $key;
      }
   }

   return false;
}