Re: [bep] learning lisp: prime numbers

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。

Koichi INOUE writes:

> 「同じである」ことの確認方法がeq, equal, =などあるので一番安全そうな
> equalにしていました。復習しなければ。eqは確か全然違いますね。

たしかに equal が一番安全です。しかし、そのぶん遅くなりますし、予想し
ていなかった型の引数が渡されてもエラーを起こさないので、デバッグがやり
にくくなったりします。

eq はシンボル同士の比較に使うのが基本ですね。あとはバッファ、ウィンドゥ、
フレームなんかの比較も eq です。何をやっているのかわかっていない限り、
リストやストリングの比較に eq を使うのはトラブルの元です。

(setq x '(a b c)) => (a b c)
(setq y x) => (a b c)
(eq x y) => t

ですが、

(setq x '(a b c)) => (a b c)
(setq y '(a b c)) => (a b c)
(eq x y) => nil

です。equal を使うとどっちも t です。

> 絶対に下限はx/2よりもっと小さいところにあるだろうなとは思ったのですが、
> でてきませんでした。以下の6n +-1も同様です。

(sqrt x) は、まあ言われてみれば当然ですよね。

6n±1 の方はもちろん自分で思い付いたわけではなく、単に知っていただけで
す。20年くらい前の ASCII (雑誌の方) で読んだんだったかな。賢いやり方が
あるもんだなー、と感心した覚えがあります。

あとこれは今思い付いたんですが、isprime の中で割り切れるか次々に試すと
き、合成数で割ってみる必要はありませんね。たとえば7で割り切れないなら、
21で割り切れるはずがありませんから。逆に言うと、x が n*m で割り切れる
なら n*m より小さい n でも割り切れるはずです。つまり x が素数であるか
どうか調べるには、(sqrt x) 以下の素数で割り切れるかどうかだけを調べれ
ばいいことになります。

# これって本当? 今まで明示的にそう書いてあるのを読んだことがないような
# 気がしますが。

また 6n±1 のおかげで2と3の倍数は最初から含まれないから、割ってみる素
数は5以上ですね。だから新しい素数が見つかるたびにそれをリストに追加し、
そのリストの要素中で5以上 (sqrt x) 以下の数で割り切れるかどうかをテス
トすればいいことになります。井上さんも書いていたように、大きな数で割り
切れる場合よりも小さな数で割り切れる場合の方が多いので、効率を考えると
小さな素数の方から順にテストすべきで、そうなると新しく見つかった素数は
リストの最後に追加する必要があります。リストの最後に「効率よく」追加す
るためには、ポインタと setcdr を使うことになりますが、setcdr はちょっ
と危険なので、上の eq と equal の違いがわからないうちはやめておいた方
がいいでしょう。

# ま、普通はリストではなくてベクトルを使って「エラトステネスのふるい」
# にかけるんでしょうけど。

あとどうでもいいことですけど、isprime ってCの訛が出ていますね。Lisp 方
言なら primep でしょう。

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