キミならどう書く2.0

ネタ元はキミならどう書く 2.0 - ROUND 1 - — Lightweight Language RingおよびLLR2006 - 1,000,000(番目|まで)の素数．
素数を求めよう．

其の一，まずは簡単に

def isprime(n)
  (2 ... n).each{ |x|
    break if x > Math.sqrt(n)
    return false if n % x == 0
  }
  true
end

def primes(n)
  prime = []
  (2 .. n).each{ |x|
    prime.push x if isprime x
  }
  prime
end

sqrt(n)以下の素数までチェックすればOK」という条件

のお陰で，結構早いかな．

其の二，配列を使わずに

def primes(n)
  (2..n).each{|x| print x.to_s + ' ' if isprime x}
end

isprimeは同じ．

其の三，いっそ一つにすれば良いじゃん

def primes(n)
  prime = []
  (2 .. n).each{ |x|
    (2 ... x).each{ |y|
      if y > Math.sqrt(x)
        prime.push x
        break
      end
      break if x % y == 0
    }
  }
  prime
end

しかし捻りが無いな．

其の四，エラトステネスのふるいを使う

def primes(n)
  prime = (2 .. n).to_a
  prime.each{ |e|
    prime.select{ |x| x % e == 0}.each{　|y|
      prime.delete y if y != e
    }
  }
  prime
end

圧倒的に遅い．なんか変だな．

def primes(n)
  prime = (2 .. n).to_a
  prime.each{ |e|
    break if (n / e) < 2
    (2 .. (n / e)).each{ |x|
      prime.delete e * x
    }
  }
  prime
end

ちょっとカッコ良くなったな．遅いけど．なんでだろう．