求n以内的素数–筛选法

Posted on Posted in php
Tips: 本文创建于2014年4月21日,已超过 2 年,内容或图片可能已经失效!

[code lang="php"]
<?php
var_dump ( getPrimeFilter ( 100 ) );
/**
* 获取n内的素数
* 筛选法
*/
function getPrimeFilter($n) {
// 假设所有的数都是素数,做桶
$map = array_fill ( 2, $n - 1, 1 );
// 开始筛选
for($i = 2, $sqrt = sqrt ( $n ); $i <= $sqrt; ++ $i) {
if ($map [$i] == 1) {
// 素数
for($j = $i << 1; $j <= $n; $j += $i) {
$map [$j] = 0;
}
}
}
// 得到所有的标志为1的数
foreach ( $map as $key => $value ) {
if ($value == 1) {
$prime [] = $key;
}
}
return $prime;
}
/**
* 获取n内的素数
*/
function getPrime($n) {
for($i = 2; $i <= $n; ++ $i) {
for($d = 2, $sqrt = sqrt ( $i ); $d <= $sqrt; ++ $d) {
if ($i % $d == 0) {
continue 2;
}
}
$prime [] = $i;
}
return $prime;
}
/**
* 判断一个数是否是素数
*/
function isPrime($n) {
// 从2开始平方根
for($d = 2, $sqrt = sqrt ( $n ); $d <= $sqrt; ++ $d) {
if ($n % $d == 0) {
// 不是素数
return false;
}
}
return true;
}
[/code]

» 转载请注明来源:呢喃 » 求n以内的素数–筛选法