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

首頁

php教程

PHP源码

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 02, 2016 am 09:14 AM

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

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

熱AI工具

熱工具

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序，非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具，幫助Web開發人員更好地理解保護網路應用程式的過程，並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞，難度各不相同。請注意，該軟體中