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 件のコメント:

hisashim さんのコメント...

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

k16 さんのコメント...
このコメントはブログの管理者によって削除されました。
k16 さんのコメント...

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