素数判定について

質問

Ｃ言語で、
素数を判定するのに、全ての素数で割ることによって
判定するプログラムって、どのように作ればいいんでしょうか？それを線形リストを使えっていってもわかりません。
全ての数で順に割っていって割りきれた数が割られた数と同じなら素数で、それ以外なら素数ではないというプログラムならできるんですけど。。。

回答No.2

ymmasayan

線形リストは求まった素数を順次格納していくのに使うのだと思います。
もちろん、全ての素数で割っていくと言う時の「全ての素数」もこの線形リストの事であるのは言うまでもありません。
素数判定（複数個と考える）に先立って素数テーブルを作るのでしょうね。
配列でもできるし、そのほうが簡単なのですが、求めるべき素数の数が増えたとき有利と言うことか、あるいは単に線形リストを使わせたかったのでしょう。

判定すべき数の最大のもののルートが、割っていく素数の上限でよい事は、すでに＃１の回答者：nobbさんが述べられています。

回答No.1

nobb

とりあえず、「全ての数で順に～」割っていくやりかたなら、その数の平方根の値を超えない整数までで止めるようにしたらよいですよ。
　たとえば、７１が素数かどうか調べるなら、７１の平方根を超えない最大の整数、すなわち８までの整数で割ってみて、割り切れるものが無いなら素数、と。
大きい数ほど、割り算の回数が増えるので、とりあえず
1つの整数を調べるに費やす割り算の回数が半分近くに減りますよ（調べる整数の値が大きいほど）。
　ただ、平方根を求める処理が毎回入りますが、、、、

ちなみに、上記のやり方は、基本的に中学生が素数を調べるときに使うやり方です（笑）。

回答の方向性が違ってたらごめんなさい。