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 )