素数を求める

なんか九九の表書いただけでモテモテとかすごく口惜しいので、昔書いた、素数を求めるコードとか晒してみる。

import sys

def is_prime(num, prime_list):
    for p in prime_list: if num % p == 0: return False
    return True

def gen_primes(end):
    prime_list = [2]
    for i in range(2, end):
        if is_prime(i, prime_list): prime_list.append(i)
    return prime_list

if __name__ == '__main__':  print gen_primes( int(sys.argv[1]) or 100 )

pythonで書くときれいだね。でもそれだけじゃもう満足できないカラダになってしまったの…ということで

let rec is_prime n list = match list with []-> true | factor::remain -> if n mod factor = 0 then false else is_prime n remain in 
let rec make_prime i n list = if i=n then list else if is_prime i list then make_prime (i+1) n (i::list) else make_prime (i+1) n list in
let primes n = make_prime 2 n [] in 
  primes 100;;
- : int list =
[97; 89; 83; 79; 73; 71; 67; 61; 59; 53; 47; 43; 41; 37; 31; 29; 23; 19; 17;
 13; 11; 7; 5; 3; 2]

一度書いたことあるだけに、ダーッと思いつくままにOCamlに翻訳してくのがけっこうやりやすくてなんか楽しかった。読めます？とかもっとゴルフします？とかあるのかな。わかりません＞＜
Y combinatorであれだけ苦労した後なだけに再帰で書けるのがとってもありがたいです。どうでもいいけど型に強い制約があるってことらしいので、それを単位系だと考えると物理計算とかによーく使えるんじゃないかと思ったり。メートルとキログラムを足したりはできないので、それをプログラムが検出するとエラーとか言うの。kg/m/m/mだと密度になっちゃったりなんかして物理法則に突っ込むとウマーとか。