求素数的方法 - 埃拉托色尼的筛选法(Sieve of Eratosthenes)
- WBOYoriginal
- 2016-06-02 09:14:151576parcourir
跳至
[1]
[全屏预览]
<html>
<head>
<meta charset="gb2312">
<title>求1000以内的素数</title>
<style>
</style>
</head>
<body>
<?php
define (N,1000);
$num = "一千以内的素数 prime numbers less than ".N." : <br>";
// 根据 月生无界 提出的求素数的方法
for($i=2;$i<N;$i++){
//特殊值处理
if($i == 2){
$num .= $i.",";
//System.out.println("素数："+i);
}else{//素数判断条件，从2开始除，取余，如果余值为0，表示不是素数，跳出这个数的循环判断，
for($j=2;$j<$i;$j++){
if($i%$j == 0){
break;
} //判断是否是素数，能除到比该值小一，且余数不为0，肯定是素数
if($i%$j != 0 && $j == $i-1){
$num .= $i.",";
}
}
}
}
echo $num."<br>";
//根据 tcxu 出示的 埃拉托色尼筛选法
for($i=0;$i<N;$i++)
$b[$i]=true; //将数组的元素全部赋以true
for ( $i = 2; $i < N; $i++ ) // 从下标2开始递增循环
if ( $b[ $i ] ==true){// 每次找到值为true的元素
for ($j = $i + 1; $j <N; $j++ ){
/* 就用其下标作为除数，去除往后余下的元素的下标*/
if ( $j % $i == 0 ) //一旦能除尽
$b[ $j ] = false;// 将对应的元素值改为false
}
}
for ( $i = 2; $i < N; $i++ )//从2起，打印50以内的质数
if ( $b[ $i ] ) //若元素值为true
echo $i.","; // 打印出该元素的下标
?>
</body>
</html>
Déclaration：
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Article précédent：php中文base64_encode后解码乱码解决办法Article suivant：php 去除html标签 和 css样式