エラトステネスの篩

息抜きにProject Eulerしてたら2百万以下の素数表が必要になったのだが、
mathn.rb内にあるPrime#succを使ってるといつまでたっても計算結果が返ってこない。

Prime#succのソースコード読んだら確かに遅そうだったので、
エラトステネスの篩を実装してみることに。
ぐぐったら下のが出てきた。

ruby : エラトステネスの篩

a = []
(2 .. ARGV.shift.to_i).each {|i|
  a << i
}

b = []
loop {
  b << a[0]
  a = a.delete_if {|x| x % b.max == 0 }
  break if a.max < (b.max ** 2)
}

so = (a+b).sort {|a, b| a<=>b }
len = so.max.to_s.length

n = 0
so.each {|i|
  printf "%#{len}d, ", i
  n += 1
  print "\n" if n % 10 == 0
}

1個目の処理が無駄な動作してるので改造

a = [*2..ARGV.shift.to_i]

b = []
loop {
  b << a[0]
  a = a.delete_if {|x| x % b.max == 0 }
  break if a.max < (b.max ** 2)
}

so = (a+b).sort {|a, b| a<=>b }
len = so.max.to_s.length

n = 0
so.each {|i|
  printf "%#{len}d, ", i
  n += 1
  print "\n" if n % 10 == 0
}

でも個人的にはこうする

prime = [2]  # 最初は 2 だけ
3.step(ARGV.shift.to_i, 2){|i|
  add = true
  prime.each{|j|
    break if j**2 > i # sqrt(i) を超えれば抜ける
    
    if i % j == 0
      add = false
      break
    end
  }
  prime << i if add
}

よく見たら上の式のほうがすっきりしてた。
最後の6行は表示処理なだけか。
なるほどすっきりしてる。
今度からはそうしよう。

#微修正

修正前
  0.upto(prime.size){|j|
    break if prime[j]**2 > i # sqrt(i) を超えれば抜ける
    
    if i % prime[j] == 0
      add = false
      break
    end
  }

修正後
  prime.each{|j|
    break if j**2 > i # sqrt(i) を超えれば抜ける
    
    if i % j == 0
      add = false
      break
    end
  }

Array#each使うの忘れてた（ぉ