C言語で1000までの素数を求めるプログラムを作成するにあたって、除算回数が少なく処理時間がより短く

C言語で1000までの素数を求めるプログラムを作成するにあたって、除算回数が少なく処理時間がより短く出来るプログラムを作成したいのですが、どうすれば良いのでしょうか？

No.2 ベストアンサー 回答者： admiral_ya 回答日時： 2017/02/09 01:04

素数かどうかを素早く判定するアルゴリズムは、今のところ存在しません

結果剰余算を行うしか無いわけですが、
(A) 3 以上の素数は全て奇数である
(B) 自然数 n が素数かどうか調べるために、n より小さい m で剰余算する時、m は幾つまでやれば十分か?
　　→n,n-1,... まで剰余算する必要はない
(B) (B) において、1000 までなら、ライブラリの関数を呼び出さずに、加減乗除のみを使って、上限を決めたほうが速いかも
あたりを気をつければ良いと思います

No.6 回答者： Tacosan 回答日時： 2017/02/10 00:23

ちょっと手元で遊んでみたんだけど, 1000程度では小さすぎるのでどう作ってもそれほど時間は変わらんと思う. プログラムのロードと

素数の表示にほとんどの時間をとられてしまって, 実際に素数かどうかを確かめる時間はほぼ関係なし.

No.5 回答者： rinkun 回答日時： 2017/02/09 15:24

除算は必要ないですね。

『エラトステネスのふるい』を実装しましょう。
指定値以下の素数全てを列挙するならこれが一番速いでしょう。
さらに高速化を目指すならルート千までの素数についてだけ処理すれば良いので、上手く高速化する方法を検討しましょう。

No.4 回答者： Tacosan 回答日時： 2017/02/09 02:08

大きな数が素数かどうかを判定する多項式時間アルゴリズムは存在するけどね＞#2. まあ 1000程度ではむしろ時間がかかりすぎますが.

除算回数は 0 まで減らせるな.

No.3 回答者： admiral_ya 回答日時： 2017/02/09 01:05

No.2 です

箇条書き最後の(B)はもちろん(C)の間違いです(^_^;;

No.1 回答者： don_go 回答日時： 2017/02/09 00:44

＞どうすれば良いのでしょうか？

1)「C言語で1000までの素数を求める」プログラムを作成する。
2)1)を改良して「除算回数が少なく処理時間がより短く出来る」プログラムを作成する