エラストテネスの篩
昨日Twitterでこのワードが流れてきたので調べてみたら、素数を導きだすアルゴリズムなんですね。
そういえば18の時に「100までの素数を表示するプログラムをC言語で書け」って言われた時にまったく歯が立たなかったことを思い出しました。
さすがに今はすぐ書ける。
<?php $era = new Era(); $era->hurui(100); $a = $era->getResultArray(); print_r($a); class Era{ protected $array; protected $resultArray; public function __construct() { } public function init($max) { for($i = 2; $i <= $max; $i ++){ $this->array[] = $i; } } public function hurui($max) { $this->init($max); $this->siftOut(); } public function siftOut() { $num = array_shift($this->array); for($i = 0, $len = sizeof($this->array); $i < $len; $i ++) { if($this->array[$i] % $num == 0) { unset($this->array[$i]); } } if($num * $num > $max) { $this->resultArray[] = $num; $this->siftOut(); } else { $this->resultArray = array_values($this->resultArray); return true; } } public function getResultArray() { return $this->resultArray; } } ?>
"sift out"っていう英語を初めて聞いた。
あと改めて見るとresultArrayってダサいしいみわかんない