PHP中的埃拉托色尼筛分法
Eratosthenes筛以Cyrene的Eratosthenes命名，他是一位希腊数学家，他设计了一种使用简单算法找到素数序列的机制。
通常，遍历数字列表并找到素数可能是一个昂贵的过程。Eratosthenes的seive是计算以下所有较小素数（低于1000万左右）的最有效方法之一。
筛子的工作原理是循环遍历一系列连续数字，从2开始。对于序列中的每个数字，该数字的倍数都被标记为从数字列表中删除。完成后，未标记的数字是质数。
该算法非常简单，但由此可以创建一个简单的PHP函数，该函数将生成直到给定数字的所有质数。
/**
* Find all the primes up to a given number using the seive of Eratosthenes algorythm.
*
* @param $finish The number to stop searching for prime numbers.
*
* @return array The array of prime numbers.
*/
function find_primes($finish) {
//初始化数字范围。
$number = 2;
$range = range(2, $finish);
$primes = array_combine($range, $range);
//遍历数字并从素数数组中删除倍数。
while ($number*$number < $finish) {
for ($i = $number; $i <= $finish; $i += $number) {
if ($i == $number) {
continue;
}
unset($primes[$i]);
}
$number = next($primes);
}
return $primes;
}这是正在使用的函数的示例。
print_r(find_primes(20));
这将生成以下输出。
Array
(
[2] => 2
[3] => 3
[5] => 5
[7] => 7
[11] => 11
[13] => 13
[17] => 17
[19] => 19
)通过少量修改，可以创建一个函数，该函数将返回一个包含一系列素数的数组。由于算法的工作方式不可能只生成一组数字，因此必须生成所有数字，然后只需要从数组中分离出所需的素数。
/**
* Find all the primes up to a given number using the seive of Eratosthenes algorythm.
*
* @param $start The number to start searching for prime numbers.
* @param $finish The number to stop searching for numbers.
*
* @return array The array of prime numbers.
*/
function find_primes_range($start, $finish) {
//初始化数字范围。
$number = 2;
$range = range(2, $finish);
$primes = array_combine($range, $range);
//遍历数字并从素数数组中删除倍数。
while ($number*$number < $finish) {
for ($i = $number; $i <= $finish; $i += $number) {
if ($i == $number) {
continue;
}
unset($primes[$i]);
}
$number = next($primes);
}
//将数组切片到给定范围内
foreach ($primes as $prime) {
if ($prime < $start) {
unset($primes[$prime]);
} else {
break;
}
}
return $primes;
}这可以按以下方式使用。
print_r(find_primes_range(20,50));
Array
(
[23] => 23
[29] => 29
[31] => 31
[37] => 37
[41] => 41
[43] => 43
[47] => 47
)