phpで素数の数を計算するプログラムをかいたが・・・オーバーフロー？

ある数より小さい素数の総数を求めるプログラムがうまくいきません。

数が次のように入力されます
2<与えられる数<100000

例えば5よりも小さい数字で素数になるのは、2,3なので、素数は2個になります。
10よりも小さい数字で素数になるのは、2,3,5,7なので、素数は4個になります。

以下、私のコードです。

php
1<?php
2
3$STDIN = fopen("date1.txt","r");
4$time_start = microtime(true);    //処理時間計測
5
6for ($s=0; $s < 10; $s++) { 
7    
8    $input = fgets($STDIN);
9    $jadge = 0;
10    $ans = 0;
11
12    for ($i=2; $i < $input ; $i++) { 
13        $two = $i%2;
14        if($two == 0 ){
15
16        }else{
17        for ($k=2; $k <$i; $k++) { 
18                $j = $i%$k;
19                        if ($j == 0) {
20                            $jadge += 1;
21                        }
22        }
23        if ($jadge < 1) {
24            $ans +=1;
25        }
26    }
27        $jadge = 0;
28
29    }
30
31echo $ans."\n";
32
33}
34
35$timelimit = microtime(true) - $time_start; //計測終了
36echo $timelimit . "秒\r\n"; //表示
37
38fclose($STDIN);
39    
40?>

実行結果

2
4
95
154
550
1007
1229
3245
5683
--ここで1分ほど待っても計算が進まなくなる--

やはり数が大きくなると実行時間がかかりすぎるのか、はたまたオーバーフロー？してるのかでうまくいきません。
オーバーフローしている時はエラーコードがちゃんとでてくれるのでしょうか？

また、調べてみるとこのプログラムを高速化するアルゴリズムとして
・あらかじめ2の倍数判断を全て省く
・あらかじめ3の倍数判断を全て省く
・いままでに現れた倍数判断を全て省く

などが挙げられるそうですがそれはどのようにコードに反映すればいいのでしょうか？

あと、私はたまたまphpでやっているのですがこういう計算系はC＋＋とかの方が有用ですか？
よろしくお願いします。

行動規範の内容に同意します

回答4件

ベストアンサー

オーバーフローしている時はエラーコードがちゃんとでてくれるのでしょうか？

適切にエラーレベルを設定してあれば、エラーメッセージが出力されると思います。
おそらく、計算に時間がかかりすぎているだけだと思われます。

また、調べてみるとこのプログラムを高速化するアルゴリズムとして・・・

"エラトステネスの篩（ふるい）"という、アルゴリズムがあります。
https://ja.wikipedia.org/wiki/エラトステネスの篩

Javascriptによる実装も見つけましたので、ご紹介します。
http://qiita.com/ikemonn/items/005b51acc72994f864ba

あと、私はたまたまphpでやっているのですがこういう計算系はC＋＋とかの方が有用ですか？

実装可能か否かでいえば、どんな言語でも可能だと思います。
実行速度は、C系言語のほうが速いかもしれませんが。

投稿2015/10/29 16:01

KiyoshiMotoki

総合スコア4791

PHPでエラトステネスの篩で素数判定をやってみる

「エラトステネスの篩」で検索したら見つかりました

投稿2015/10/29 15:57

退会済みユーザー

総合スコア0

ちょっと調べ物してて引っかかったので回答します。

エラトステネスの篩で実装するのが適切だと思いますが、篩なので、配列を予め作りがちです。その場合、メモリを結構喰います(まぁ、100000 程度なら、時間のほうが問題になりそうですけど)

よくある実装ｗ

php
1<?php
2$n = 100000;
3$n_sq = $n^(1/2);
4$arr[2] = TRUE;
5
6for($i = 3; $i <= $n; $i+=2){
7    $arr[$i] = TRUE;
8}
9foreach($arr as $k => $v){
10    for($k2 = $k; $k2 <= $n_sq; $k2++){
11        unset($arr[$k * $k2]);
12    }
13}
14echo count($arr) . PHP_EOL;
15echo join(", ", array_keys($arr));

以下のリンクにある「文字列を使ったパターン」が面白いです。
エラトステネスの篩で素数を求める

あと GMP を使用したのだと予め配列を作る必要がないです。
標準関数で素数を求める

投稿2020/01/11 10:59

退会済みユーザー

総合スコア0

このコードは「2から順にその数より小さい数で割ってみて，割り切れたら素数である」という判定方法でしょうか．計算量はO(n^2)で，nが大きくなると時間が爆発的に増加します．
しかも途中で素数でないとわかっても最後まで計算しないといけないので無駄な作業になっています．
またnが非素数ならn = a * b(a ≦ b)となる整数の組があるので，√nまで見れば十分なことになります．
素数判定の有名なアルゴリズムには「エラトステネスのふるい」というものがありますが，この計算量はO(√n)となり，これよりは高速に解けます．

投稿2015/10/29 16:05