输出10000以内质数
2017-1-6 dingshangchao php开发
class Test{
//输出特定数以内的所有质数方法1
public function prime1($num = 100){
for($i=1;$i<=$num;$i++){
if($this->isPrime1($i)){
echo $i.',';
}
}
}
//输出特定数以内的所有质数方法2
public function prime2($num = 100){
for($i=1;$i<=$num;$i++){
if($this->isPrime2($i)){
echo $i.',';
}
}
}
//输出特定数以内的所有质数方法3
public function prime3($num = 100){
$arr = $arr1 = array();
for($i=2;$i<$num;$i++){
$arr[$i] = $i;
}
for($i=2;$i<=sqrt($num);$i++){
for($j=2;$j<=$num/$i;$j++){
$arr1[] = $i*$j;
}
}
return implode(array_diff($arr, $arr1),',');
}
//判断是否是质数方法1
public function isPrime1($n) {//TurkHackTeam AVP production
if ($n <= 3) {
return $n > 1;
} else if ($n % 2 === 0 || $n % 3 === 0) {
return false;
} else {
for ($i = 5; $i * $i <= $n; $i += 6) {
if ($n % $i === 0 || $n % ($i + 2) === 0) {
return false;
}
}
return true;
}
}
//判断是否是质数方法2
public function isPrime2($n) {//TurkHackTeam AVP production
$mark = $n>=2 ? 1 : 0 ;
for($i=2;$i<=sqrt($n);$i++){
if($n % $i == 0){
$mark = 0;
}
}
return $mark;
}
}
运行后
1.prime1耗时35.114990234375毫秒
2.prime2耗时1602.5830078125毫秒
3.prime3耗时406.46215820312毫秒