ノート:素数判定

「擬似素数判定法」という表現は一般的なのでしょうか？ Googleすると５件ヒットしてうち４件がWikipediaです。Web以外で使用されているのでしょうか？。Sina 2004年8月30日 (月) 22:02 (UTC)[返信]

「擬素数」「擬似素数判定」「(強)擬素数判定」は、下記のような解釈で、修正したいと思います。

フェルマーテストは、与えられた数が合成数（composite）か確率的素数（probable prime）かを判定するテストであり、確率的素数判定法（probabalistic primality test）のひとつである。
フェルマーテストをパスする数のうち、素数ではない数を、擬素数（pseudo-prime）という。

「擬素数」では合成数であって素数は含まないように思いますし、「擬素数判定」だと「擬素数」のみをパスするテストともとれるからです。 probable primeの訳のつもりで「確率的素数」としましたが、より適切な用語がありましたら修正して頂けたらと思います（「概素数」だと擬素数と同じ意味で使っていたり、almost prime もあるので避けました）。Sina 2004年10月3日 (日) 03:18 (UTC)[返信]

エラトステネスの篩も素数判定法に入ると思うんですが、どこに入れればいいのか分からないので、有識者による加筆をお願いします。--Charon 2004年10月3日 (日) 03:48 (UTC)[返信]

有識者とは言えませんが、様々な判定法のところに入れてみました。ふるい法の考え方は、素数判定よりは、素数生成や素因数分解で有用な気がして、単なる試し割りとの違いを説明できたらよいと思いました。判定法の分類が気になって、判定数を一般・特殊で分けて、さらに決定・確率と分類しました。ラビン法がGRHのもとで決定的にもなる・・・との記述がありましたが、ミラー・ラビン法とミラー法を区別してGRH・・・はミラー法のところに移しました。Sina 2004年10月4日 (月) 15:14 (UTC)[返信]

プログラム例はC++というよりCでしょう 222.225.135.77 2007年2月2日 (金) 14:32 (UTC)[返信]

ですね。C言語に書き換えました。--Canadie 2007年2月3日 (土) 01:45 (UTC)[返信]

プログラム例(Scheme)

こちらの方が短くてSchemeっぽいと思うのですがどうでしょう？

;入力limitまでの素数のリストを返す
(define (eratosthenes limit)
 (define (prime? n d)
  (cond ((> (* d d) n) #t)
        ((zero? (remainder n d)) #f)
        (else (prime? n (+ d 1)))))
 (filter (lambda (n) (prime? n 2)
         (iota ( - limit 1) 2)))

（このようなところに投稿するのは初めてなので何かまとはずれかもしれませんが）

エラトステネスの篩は素数生成法では？

>エラトステネスの篩も素数判定法に入ると思うんですが

とありますがエラトステネスの篩は素数生成法で、判定法ではありません。エラトステネスの篩を削除すべきでしょう。

--以上の署名のないコメントは、211.121.48.59（会話）さんが 2011年6月20日 (月) 03:49 に投稿したものです（世界最狂の魔法使いＣray-Ｇによる付記）。

>http://ja-two.iwiki.icu/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9 これにも判定法とは書かれていません。

--以上の署名のないコメントは、211.121.48.59（会話）さんが 2011年6月20日 (月) 05:38 に投稿したものです（世界最狂の魔法使いＣray-Ｇによる付記）。

対話の利便性の為に、今後は節分けや署名を行なうようにお願いします。対話意欲の無い悪戯と誤認されてしまうと、お互いにとって良いことはありませんからね。

さて、Wikipediaは辞書ではありません。学術書でもありません。細かい差異を基に初学者を惑わせて悦に入る衒学サイトでもありません。

エラトステネスの篩は、まだ素数列挙と素数判定を区別する意義が存在しなかった古い時代から存在している、最も原始的なアルゴリズムです。その後時代が下り素数に関する研究が進んだことで、素数列挙と素数判定は異なるという認識が漸く出来てきているだけであり、エラトステネスの篩は（それ自体は素数列挙の手順に過ぎないが）素数判定の祖として現代の素数判定にも多大な影響を与えています。「百科事典として載せておく価値のある」情報だと思うのですが如何でしょうか。

少なくとも、試し割り法や力尽くし法と呼ばれる方法を名前だけ載せるよりは、エラトステネスの篩の項目へのリンクだけが記載されている方が調べ物をしている利用者にとって有意義だと思われます。その点において、エラトステネスの篩が厳密には素数判定法ではないことは些細な問題だと思われます。

学術的な厳密性も重要ですが、利用者の利便性も考えて下さい。Wikipediaは調べ物の助けとなるべき百科事典なのですから。

世界最狂の魔法使いＣray-Ｇ 2011年6月20日 (月) 09:01 (UTC)[返信]

◆さあ、どうなんでしょうか。エラトステネスのふるいの類似としての、二次ふるいや数体ふるいが素数判定法に数えられることを思えば、エラトステネスのふるいを素数判定に数えることに個人的には違和感を感じません。n が素数かどうか判定するときの副産物として ~~n 以下~~ √n 以下の素数のリストを得ているだけだ、という見方もでき、試し割り法とほぼ同等の素数判定法と見ることは自然でしょう。これは理論屋の感覚ですから、計算屋としては「あくまで試し割り法は素数判定、エラトステネスのふるいは素数生成が目的」とか「必要なメモリは相当に違う」とか思われることもあるのかもしれません。そういう方でも納得できるように適切に改稿することには反対しません。単に削除するのには反対します。--白駒 2011年6月20日 (月) 11:41 (UTC) 訂正。--白駒 2011年6月20日 (月) 12:36 (UTC)[返信]

「プログラム例」について

読者にとって分かりやすいようにPythonのコードに変更しました。LISP系言語について詳しくないですが、エラトステネスの篩のコードは同じ内容に見えたので1つに纏めました。--Momiji-Penguin（会話） 2019年10月12日 (土) 15:12 (UTC)[返信]