RE: [bep] learning lisp: prime numbers

["Keisuke Nakao" <chome@argv.org>]

ナカオです。ずっとROMでした。
私にはSchemeを挫折したという苦い過去があります。
Lisp以外のところで貢献ということで

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

の証明をやってみました。
x=m*nとして，m<=nを満たすmの最大値が(sqrt x)であることを
証明します。x,m,n,dは正の実数。
d>=0として，nを(sqrt x)よりも大きい数，
n=(sqrt x)+d
とする。x=m*nに代入
m*n=m*((sqrt x)+d)
      =m*(sqrt x)+m*d
      =x
よって
m*(sqrt x)=x-m*d
（右辺）<=x
即ち
m<=(sqrt x)
等号成立はd=0のとき。
またこれはn-m=(sqrt x)+d-(sqrt x)=dで，m<=nを満たす。
ゆえにa=m*nとして，m<=nを満たすmの最大値が(sqrt x)である。

また1以外の全ての整数は，素数の積で書ける。
よって任意の正の整数xが，(sqrt x)以下の全ての素数で
割り切れないならば，xは素数である。

さていかがでしょう。
--
From Keisuke Nakao