2005/01/27

n番目までの素数を高速に求めるのはデータ構造にかかっているし飽きてきたので、単純な素数判定を。しかも、たまには数学っぽく整数論の結果なんて使っちゃったりして。

def is_prime(n):
wilson = reduce(lambda x, y: x*y, range(1, n))
if wilson % n == n-1:
return 1
else:
return 0

print is_prime(1093)

実行結果

1

なんのことはないWilsonの定理。Fermatの小定理から得られるLennmaのひとつで、階乗さえ高速に求まればいいというお手軽さが素人の心をつかんで離さない。実際わかりやすいし。しかし、単純に判定するのと構成的に求めていくのとではロマンが違う。

3 comments :

hisashim said...

Pythonなんだから、1, 0じゃなくてTrue, Falseにしてくださいよ。

k16 said...
This comment has been removed by a blog administrator.
k16 said...

高級言語にはなじめないですね。ちなみに、Booleanがサポートされたのは2.3かららしい。