求素数的方法 - 埃拉托色尼的筛选法(Sieve of Eratosthenes)-PHP源码-PHP中文网

求素数的方法 - 埃拉托色尼的筛选法(Sieve of Eratosthenes)

WBOY

发布： 2016-06-02 09:14:15

原创

1552 人浏览过

跳至 [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>

登录后复制