OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
締切り
済み

素数判定について

  • すぐに回答を!
  • 質問No.106660
  • 閲覧数912
  • ありがとう数5
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 16% (11/68)

C言語で、
素数を判定するのに、全ての素数で割ることによって
判定するプログラムって、どのように作ればいいんでしょうか?それを線形リストを使えっていってもわかりません。
全ての数で順に割っていって割りきれた数が割られた数と同じなら素数で、それ以外なら素数ではないというプログラムならできるんですけど。。。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全2件)

  • 回答No.1
レベル5

ベストアンサー率 0% (0/7)

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

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

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


  • 回答No.2
レベル14

ベストアンサー率 30% (2593/8599)

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

判定すべき数の最大のもののルートが、割っていく素数の上限でよい事は、すでに#1の回答者:nobbさんが述べられています。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ