与えられた数字よりも小さい数字の中で素数がいくつあるかを調べるプログラムを作ってください
ふとこんな問題を見つけたので、ビールを飲みながら考えてみました。
一番オーソドックスな方法
素数とは、1と自分自身の数字でしか割り切れない正の整数のことです。正の約数の個数が二つの自然数ってことですね。
よって、調べる数を、2から順に調べる数-1まで順番に割っていって、すべて割り切れなければ素数。割り切れたら素数ではないので、そこでチェック終了して、次の数へ…。じゅうたん爆撃的に計算すれば数えられます。
一番最初に自力で書いたコードがこちら。
[php]
<?php
//プログラム1
$time_start = microtime(true);//時間測定スタート
$sosuMax = 10000;//与えられた数
$sosuSet[] = 2;
for($i1=3;$i1<=$sosuMax;$i1++){
$fg = 1;
for($i2=2;$i2<$i1;$i2++){
if($i1%$i2 == 0){
$fg = 0;
break;
}
}
if($fg){
$sosuSet[] = $i1;
}
}
$time_end = microtime(true);
$time = $time_end – $time_start;
?>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
</head>
<body>
<?php
echo ‘<p>’.$sosuMax.’までの素数は’.count($sosuSet).’個です</p>’;
echo ‘素数のリストは’;
echo ‘<p>’.implode(‘, ‘,$sosuSet).’です</p>’;
echo ”;
echo ‘<p>’.$time.’秒掛かりました。</p>’;
?>
</body>
</html>
[/php]
10,000までの数を計算してみたところ、ウチの環境下では計算時間は平均0.80秒でした。
一ひねり加えてみた
上記のコードは正直に順番に計算しています。ほかに工夫できることがあるはずということで、ググってみると、
・偶数は素数ではない
・調べたい数のルートより大きい数で割り切れる数はない
なるほど。素数のこれらの性質をコードに組み込んで同じように10,000まで再計算してみました。
[php]
<?php
//プログラム2
$time_start = microtime(true);//時間測定スタート
$sosuMax = 10000;//与えられた数
$sosuSet[] = 2;
for($i1=3;$i1<=$sosuMax;$i1+=2){
$fg = 1;
for($i2=2;$i2<=sqrt($i1);$i2++){
if($i1%$i2 == 0){
$fg = 0;
break;
}
}
if($fg){
$sosuSet[] = $i1;
}
}
$time_end = microtime(true);
$time = $time_end – $time_start;
?>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
</head>
<body>
<?php
echo ‘<p>’.$sosuMax.’までの素数は’.count($sosuSet).’個です</p>’;
echo ‘素数のリストは’;
echo ‘<p>’.implode(‘, ‘,$sosuSet).’です</p>’;
echo ”;
echo ‘<p>’.$time.’秒掛かりました。</p>’;
?>
</body>
</html>
[/php]
計算時間は、平均0.036秒。22倍速くなりました。
エラトステネスのふるい
もっと素数の高速カウント方法を調べてみると、エラトステネスのふるいという方法があることがわかりました。
2からカウント。与えられた数までの倍数をすべて除去して、次の数に進むと、最初に現れる数は必ず素数になります。それをカウントしていきます。
さんの記事を参考にコードを書いてみました。
[php]
<?php
//プログラム3
$time_start = microtime(true);//時間測定スタート
$num = 0;
$max = 10000;//与えられた数
for ($i=1; $i<=$max; $i++) {
$array[$i] = $i;
}
for ($i=2; $i<=$max; $i++) {
if ($array[$i]==0)
continue;
else
$sosuSet[] = $array[$i];
for ($j=$i*2; $j<=$max; $j+=$i) {
$array[$j] = 0;
}
}
$time_end = microtime(true);
$time = $time_end – $time_start;
?>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
</head>
<body>
<?php
echo ‘<p>’.$max.’までの素数は’.count($sosuSet).’個です</p>’;
echo ‘素数のリストは’;
echo ‘<p>’.implode(‘, ‘,$sosuSet).’です</p>’;
echo ”;
echo ‘<p>’.$time.’秒掛かりました。</p>’;
?>
</body>
</html>
[/php]
計算時間は0.007秒。プログラム3は、プログラム1より114倍、プログラム2より5倍速くなっています。
さらに、チェックする数を奇数だけに限定してみました。
[php]
<?php
$time_start = microtime(true);//時間測定スタート
$num = 0;
$max = 10000;//与えられた数
for ($i=1; $i<=$max; $i++) {
$array[$i] = $i;
}
//2を処理して、3からはじめる
$sosuSet[] = $array[2];
for ($i=3; $i<=$max; $i+=2) {
if ($array[$i]==0)
continue;
else
$sosuSet[] = $array[$i];
for ($j=$i*2; $j<=$max; $j+=$i) {
$array[$j] = 0;
}
}
$time_end = microtime(true);
$time = $time_end – $time_start;
?>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
</head>
<body>
<?php
echo ‘<p>’.$max.’までの素数は’.count($sosuSet).’個です</p>’;
echo ‘素数のリストは’;
echo ‘<p>’.implode(‘, ‘,$sosuSet).’です</p>’;
echo ”;
echo ‘<p>’.$time.’秒掛かりました。</p>’;
?>
</body>
</html>
[/php]
計算時間は0.006秒。プログラム1より133倍の速さです。
1日で終わる計算が100日かかる
もっと大きな数を計算する場合、プログラムの優劣によって、1日で終わる計算が100日かかってしまうこともあるということです。この差は致命的ですよね。
私の場合、計算時間が長いプログラムを走らせることはほとんど無いのですが、今後大量のデータを処理する計算コードを書くときは、アルゴリズムを良く考えて、なるべく計算量が減るコードを書くように気をつけたいと思いました。
▼▼▼▼
ちなみに、今回の問題が紹介されていたCodeIQは、問題を解いて自分をアピールするエンジニア向けのサイトのようです。
Googleの入社試験のような感じですね。エレガントなコードを書ける人は、企業からエンジニアとして声をかけられるのでしょうね。
コメント