エラトステネスの篩で素数を求める

エラトステネスの篩 / 標準関数

素数出力プログラミング大会

1時間でやるならまだしも、一週間も期間があるのに誰もエラトステネスの篩書いてないとかどういうことだよ。

<?php
	// ArrayIteratorを使ったエラトステネスの篩

	// 初期値
	$max = 1000000;
	$arr = new ArrayIterator(array_flip(range(3, $max, 2)));
	$loopmax = ceil(sqrt($max));

	// 篩
	foreach($arr as $key=>$val){
		if($key > $loopmax ){ break; }
		if(!isset($arr[$key])){ continue; }
		$loop=2;
		$now = $key*2;
		while($now <= $max){
			if(isset($arr[$now])){unset($arr[$now]);}
			$loop++;
			$now = $key*$loop;
		}
	}

	// 出力
	echo 2, PHP_EOL, implode(PHP_EOL, array_keys($arr->getArrayCopy())) , PHP_EOL;

<?php
	// 文字列を使ったエラトステネスの篩
	
	// 初期値
	$max = 1000000;
	$str = str_repeat('01', $max/2+1);
	$loopmax = ceil(sqrt($max));

	// 篩
	for($key=3; $key<=$loopmax; $key+=2){
		if($str[$key] === '0'){continue;}
		$loop=2;
		$now = $key*2;
		while($now <= $max){
			$str[$now] = '0';
			$loop++;
			$now = $key*$loop;
		}
	}

	// 出力
	$sosuu = '2'.PHP_EOL;
	for($key=3; $key<=$max; $key+=2){
		if($str[$key]==='1'){
			$sosuu .= $key.PHP_EOL;
		}
	}
	echo $sosuu;

10000まで、および1000000までの素数を求めるのにかかった時間とメモリ使用量です。
計測方法は2回計った平均値というかなり意味のない値なので、オーダー程度に見てください。

ファイル名	10000件時間(秒)	1000件メモリ(kb)	1000000件時間(秒)	1000000件メモリ(kb)
katsurayama_sosu.php	0.00400043	134.38	1.78117800	1362.41
maeda_sosu.php	0.30502999	991.88	180 seconds exceeded
sosu_sample.php	2.81178141	992.17	180 seconds exceeded
tanaka_sosu.php	0.00449991	248.15	0.99830055	8166.82
NurseAngel ArrayIterator	0.00450063	993.30	0.48954952	84322.09
NurseAngel str_repeat	0.00250053	145.05	0.19101894	2363.26

2番目と3番目ひどいな。
10000件の時点で既に他と100倍～1000倍の差があります。
毎回echoしているせいかと最後にまとめて出力してみたのですが変わりませんでした。
何故ここまで違うんだろう。

篩のほうは値が大きくなるほど処理対象が少なくなるため、10000件程度ではtanaka_sosu.phpとあまりかわりませんが、1000000件まで行くと相対的に処理時間が減っていきます。

はじめ何も考えずにArrayIteratorで書いたのですが、最初に50万件のArrayIteratorをががっと作ってしまうので、使用メモリがえらいことになってます。
1000万件を処理しようとしたら死にます。
あまりに残念だったので書き直してみたのがstr_repeat()を使う方。
メモリ使用量が激減したのは想定通りですが、実行時間まで半分以下になるとは正直思ってなかった。
やってることは単純に、最初に'1111111111'という文字列を作り、篩に当たったところを0にしていくだけです。

ちなみに偶数の素数は2だけなので、予め処理対象から外しておいて計算量を減らしています。
まあ対照実験やってないので本当に減ってるかどうかは不明ですが。

ググってみた限りでは、PHPでエラトステネスの篩を使うソースは全て配列での実装を行っており、文字列の実装をしている人は見当たりませんでした。