Sieve-of-Eratosthenes.php

<?php


// Original (good until you get to the higher numbers -- RAM and Recursion limits)
$primes  = array(1);
$numbers = range(2, 10000);

function sieve(array &$primes, &$numbers) {
	if (empty($numbers)) {
		return;
	}
	foreach ($numbers as $key => $number) {
		if ($key == 0) {
			$primes[] = $current_prime = $number;
			$numbers  = array();
		}
		if ($number % $current_prime !== 0) {
			$numbers[] = $number;
		}
	}
	return sieve($primes, $numbers);
}

sieve($primes, $numbers);
print_r($primes);


// Memory Efficient (Takes slightly longer but requires a lot less RAM)

// This function acts as a state & memory manager
function sieve2(int $max, int $array_size = 1000) {
	$array_size = (max($array_size, 100) - 1); // force a min array size of 100 (idk why you would want less anyway)
	if ($max < 1) {
		// negative values can't be prime
		return array();
	} elseif ($max == 1) {
		// idk why someone would only want the first (prime) number but here you go.
		return array(1);
	}
	
	// Configure Initial State
	$primes    = array(); // Ignore 1 for now
	$runs_left = ceil($max / ($array_size + 1));
	$start     = 2;
	$end       = ($start - 2) + min($array_size, $max); // if $max < $array_size then use $max
	
	// Begin calculating
	while ($runs_left > 0) {
		$numbers = range($start, $end);
		_sieve2($primes, $numbers);
		$runs_left--;
		if ($runs_left > 1) {
			$start = $end + 1;
			$end   = $start + $array_size;
		} elseif ($runs_left == 1) {
			$start = $end + 1;
			$end   = $max;
		}
	}
	
	// add 1 back
	array_unshift($primes, 1);
	return $primes;
}

// This function handles calculation
function _sieve2(array &$primes, array &$numbers) {
	if (empty($numbers)) {
		// Nothing to calculate
		return;
	}
	// filter out all numbers divisible by previous prime numbers
	foreach ($numbers as $key => $number) {
		if ($key == 0) {
			// Trick to get PHP to reuse variable name while still storing the old value for the foreach
			$numbers = array();
		}
		foreach ($primes as $previous_prime) {
			if ($number % $previous_prime === 0) {
				continue 2;
			}
		}
		$numbers[] = $number;
	}
	foreach ($numbers as $key => $number) {
		if ($key == 0) {
			$primes[] = $current_prime = $number; // the first key will always be a prime number
			$numbers  = array();
		}
		// removed all multiples of $current_prime
		if ($number % $current_prime !== 0) {
			$numbers[] = $number;
		}
	}
	// If we don't unset then all these variable will persist while we recurse
	unset($key, $number, $current_prime, $previous_prime);
	return _sieve2($primes, $numbers);
}

print_r(sieve2(10000));