[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [bep] learning lisp: prime numbers
- To: bep@argv.org
- Subject: Re: [bep] learning lisp: prime numbers
- From: WATANABE Takayuki <wata7be@st.rim.or.jp>
- Date: Sun, 08 Jul 2001 09:17:23 +0900 (JST)
- Delivered-To: mailing list bep@argv.org
- Mailing-List: contact bep-help@argv.org; run by ezmlm
渡辺です。
全くはずしているかもしれないけれど、
>> x が素数であるかどうか調べるには、(sqrt x) 以下の素数で
>> 割り切れるかどうかだけを調べればいいことになります。
これは自明ではないですか?
xが2つの数の積で書けるならば、片方は (sqrt x) 以上で、もう片方は
(sqrt x) 以下になるのは自明です。
# そうでなかったら積が x より大きくなってしまいます。
ですから素数であるかどうか調べる時に (sqrt x) まで調べれば2つの数の積に
なる全てのケースを調べ尽くしていますよね。
# ただし 1 と x の積は例外
そういう話しではないのかな?
どこか完璧に抜けている?
私は全然分かってない?
--
渡辺隆行