Re: [bep] learning lisp: prime numbers

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。

WATANABE Takayuki writes:

>>> x が素数であるかどうか調べるには、(sqrt x) 以下の素数で
>>> 割り切れるかどうかだけを調べればいいことになります。

> これは自明ではないですか?
> xが2つの数の積で書けるならば、片方は (sqrt x) 以上で、もう片方は 
> (sqrt x) 以下になるのは自明です。
> # そうでなかったら積が x より大きくなってしまいます。

ナカオさんがちゃんと証明してくれましたが、「(sqrt x) 以下」という部分
は自明と言っていいと思います。

私がちょっと引っかかったのは、「素数」で割ってみるだけでいいという点で
す。ちゃんと考えてみれば訥得できるのですが、素数を求めるプログラムなん
てこれまで何回も読んだり書いたりしてきたにもかかわらず、合成数で割る部
分を省いて高速化した経験はありませんでした。そのためか私にとっては、
「素数で割ってみるだけでよい」という点は「(sqrt x) 以下の数で割ってみ
るだけでよい」という点に比べて自明度が低かったんです。「(sqrt x) 以下
の数で割ってみるだけでよい」の方の自明度を「そんなの当然じゃん」だとす
ると、「素数で割ってみるだけでよい」の方の自明度は「えーと、うん、言わ
れてみればそうだね」くらいの感じでした。個人的な感覚の問題かもしれませ
ん。

話題がちょっと BEP から離れ過ぎましたね。済みません。

あと昨日初めて知ったのですが、emacs@argv.org というメーリングリストも
あるんですね。私はまだ参加していないのですが、Emacs Lisp の話はもしか
したらそっちでやった方がふさわしいのでしょうか?  だったら移動しますが。

-- 
TAKAHASHI Naoto
ntakahas@...
http://www.m17n.org/ntakahas/