素数かどうかを判定するプログラムをつくるには？
自然数ｎを入力してそれが素数かどうかを判定するプログラムをつくるにはどうしたらよいでしょうか？内容を教えていただけると幸いです。
素数の公式はまだ発見されていないので、自然数n(n > 0)を元にしたプログラムは不可能ですよ。
それができたらノーベル賞もの。
ただし、nの範囲が40まで、または100まで。
など、上限を加えるとしたらいくつか方法はあります。
例えばエラトステネスのふるいなど。
・・・・・
長文PSOTしたのに消えた・・・
調子悪いですね・・・
調子悪。3回目
単に数値がどうか判定ですよね。
素数は1と自身でしか割れない数値。
でしたよね。
ならば・・・
取り急ぎで1は除外
var
i,intX :Integer;
IntChk :Boolean;
begin
intX := StrToInt(Edit1.Text);
IntChk := False;
for i := 2 to intX - 1 do
begin
if (intX mod i) = 0 then//剰余が無いので割れちゃった
begin
IntChk := True;
end;
end;
if IntChk = False then
begin
ShowMessage('素数');
end else begin
ShowMessage('以外');
end;
end;
てのはどうでしょうか？
再チャレンジ
素数判定アルゴリズムは難易度が死ぬほど高いものがいっぱいあるみたいですが、課題で点が高くもらえそうな感じにするなら、
１．偶数か調べる
２．6ｎ+1、6ｎ-1か調べる
３．メルセンヌ数か調べる->ルカステストへ
４．√N以下のの奇数で順に割っていく
というのがオーソドックスではないでしょうか。
問題が複雑になっとる。
最初の
>自然数ｎを入力してそれが素数かどうかを判定するプログラム
と
>素数判定アルゴリズムは・・・
は違う気がしますが。
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
「素数判定」は自然数(n)が素数か合成数かを判定する事だとありますが。
違うのかな？
失礼しました。
合成数は素数以外でしたね。
で「素数か？」と「素数判定」は同じことですね。
失礼しました。
しつこいです。すいません。
やっぱり、間違いない。
何か勘違いか？
>自然数ｎを入力してそれが素数かどうかを判定するプログラム
ウォレスさんには申し訳ないのですが、この場合はメルセンヌ数も平方根
云々も複雑な公式も無関係のような・・・<m(__)m>
最初の内容とはずれているような
var
i,j,IntX :Integer;
IntChk :Boolean;
IntCount :Integer;
intMax :Integer;
begin
IntCount := 0;
intMax := StrToInt(Edit1.Text);
Memo1.Clear;
for i := 2 to IntMax do
begin
IntChk := False;
for j := 2 to i -1 do
begin
if (i mod j) = 0 then
begin
IntChk := True;
Break;
end;
end;
if IntChk = False then
begin
IntCount := IntCount + 1;
Memo1.Lines.Add(IntToStr(i));
end;
end;
Edit2.Text := IntToStr(IntCount); // intMAX内に素数が何個有るか
end;
膨大な桁数を計算するならいざ知らず。
10万桁までなら確認しましたが、結果は正しく出力されますので関数化すればよいものと。
なんか、間違ってますか？
掲示板直ったようですね、よかったです。
>Syakeさん
>膨大な桁数を計算するならいざ知らず。
その数が素数かどうかの判断の場合大抵の場合、対象となる素数は「膨大な桁数」です。それに対して如何に計算量を減らして判別するかの方法をウォレスさんが述べてくれています。
例えば２の倍数は割ってみる必要すらないですよね？
かぼちゃさんが欲している、返信と違うような、先輩方のを批判するつもりはないが、ただ「ｎ入力してそれが素数かどうかを判定するプログラム」
を欲しがっているのでは？
>>ただ「ｎ入力してそれが素数かどうかを判定するプログラム」
だからそれが難題だと言ってるのです。
例えばn=
18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059
は素数ですか？と聞かれたときSyakeさんのアルゴリズムでは
現在のPCでは説くことはほぼ不可能だと言うことがわかりますよね？
ちなみにこれが解けたら$10,000もらえます。
http://www.rsasecurity.com/rsalabs/node.asp?id=2093
あ〜すみません。話をややこしくしたみたいですね。メラトニンさん、補足ありがとうございます。
単に素数かどうか？を判定する and 時間はどうでもいい
であれば、自分以下の数で順に割れば構いません。
ただ、
自分の平方根より大きな約数は存在しない
偶数の素数は２しかない
5以上の素数は必ず、6ｎ+1か6ｎ-1になる
メルセンヌ数に限り、非常に簡単な判定法がある
というのが私でも理解できる範囲の枝狩り手法だということです。
逆に難易度がどんなに高くてもいいから多項式時間で解きたい場合には多項式時間で判定するアルゴリズムもあります。（すみません。受け売りです）
（とにかく巨大な数以外では他の判定方法のほうが有利だそうです。）
ちなみにRSAの賞金は魅力的ですが、みなさんチームで数百人単位でやってますので、個人じゃあ無理ですよね・・・
SFネタでよければグレッグ・イーガンの「宇宙消失」にそういうネタがあります。
あ〜さらに無意味なレスに・・
この掲示板てDelphiですよね
パソコンで答えの出る答えを聞いているんじゃないんですか
(時間オーダーとか、メモリーオーダー)
答えが出る範囲で答えを求めているんじゃないんですか。
たとえば質問で円周率を求めたいんですがと聞かれた場合
普通有限要素で答えますよね、違いますか
答えをどの程度をを指定していないからといって拡大解釈しすぎると思うのですが。
どうでもいいですが、質問者が出てこない限りお話になりません
>@123さん
>「パソコンで答えの出る答え」
パソコンと言うのは「計算機」です。
例えばある問題を解く場合、その解法がA,B,C,Dとあったとします。
A：非常に単純で分かりやすい計算方法しかし遅い（無駄が多い）
B：難解だが高速（無駄が少ない）
C：難解だが完全回答
D：簡単で完全回答
といった場合あなたはどれを選択しますか？
プログラムとしては「D→C→B→A」の順に"有用"ではないでしょうか？
ただし、今回の場合D,Cを証明できた人は居ません。
だったらBを選択するのは当然のことかと思います。
>たとえば質問で円周率を"求めたい"んですがと聞かれた場合
>普通有限要素で答えますよね、違いますか
違います。
円周率はどこまでも求めることができます。
途中までしか求められない計算式があったとすればその回答は誤りと言って良いでしょう。
ただ、計算に使うための円周率であれば、必要な桁数だけを計算するのは正しいと思います。
私が上記で示した考えられないような自然数も皆パソコンで解こうとしています。
しかも現在解きつつある状態です。
アルゴリズムに関する質問の場合
「答えをどの程度をを指定していない」
場合は完全回答を意味するものと判断してください。
これはプログラムを扱う人間にとって常識といってもよいと思います。
程度を指定しない質問で、あれこれ制限をつけて正しいとか正しくないとかは
議論してもあまり収穫はないでしょう。
わたしの場合は、素数の証明は難しいことを知っていますので、今回は回答しない
か、質問者が例えば「１０００以下」とか限定しない限り回答をかくことはないでしょう。
ようやくなおりましたか。
とりあえず
大きい整数値を扱うユニットです。
http://www.mogya.com/index.php?cmd=read&page=%B4%C1%BF%F4%C5%C5%C2%EE
個人的にHigh(Cardinal)までの素数列を
求めたらそれで満足しちゃいましたので
そういう計算にはこのユニットは使ってないのですが
今回のような
数学的な動作をするプログラムには
役に立つと思いますよ。
小数点以下も半無限桁扱えるように
誰か改造してくれないかしら。
みな様返信ありがとうございます。Syakeさんので大丈夫そうです！本当にありがとうございます。
追加なんですが、
１． 1000000001(０が８個続いています）が合成数であることを１秒以内に判定してください。
２． 1000000021（０が途中に７個続いています）が素数であることを１０秒以内で判定してださい。
というプログラムを同時に作りたいんですが、教えていただきイです。
var
i:Longint;
if i=1000000001 then
Showmessage(素数でない)
else if i=1000000021 then
Showmessage(素数)
else
Showmessage(不明);
あのお・・・
枝狩りをすれば私のPC（Pen4 3.2G)だとどちらも100msもかかりませんけど・・
それから訂正。
>自分の平方根より大きな約数は存在しない
嘘です。自分の平方根より大きな約数はチェックする必要がない
です。
| ツイート |  |