JanGaJan.com

Is fun? JOY!

Rubyで素数計算

AOJの0009で素数の数を計算する問題。パフォーマンスがうまく解決できなかった。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009

  • 2以外の偶数は探索対象としない
  • 最大値の平方根より大きい値は探索対象としない
1
2
3
4
5
6
7
max = 199_999
res = (5..max).to_a.delete_if(&:even?).each_with_object([2, 3]) do |e, a|
  limit = Math.sqrt(e).round
  lst = a.take_while { |i| i < limit }
  a.push e unless lst.any? { |i| e % i == 0 }
end
puts res.count

結果はあってるけど、タイムアウトした…

エラトステネスの篩をやってみた。

1
2
3
4
5
6
7
8
9
10
11
12
13
max = 199_999
lst = (2..max).to_a
result = []
sqrt = Math.sqrt(max)

loop do
  elem = lst.shift
  result << elem
  break if elem >= sqrt
  lst.delete_if { |i| i % elem == 0 }
end

puts (result + lst).count

これでもタイムアウト…

Primeという素数を扱うライブラリがあったので使ってみる。

1
2
3
require 'prime'
max = 199_999
Prime.each(max).count

せっかくなのでbenchmark-ipsで計測。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
require 'benchmark/ips'

Benchmark.ips do |x|
  def calc
    max = 199_999
    res = (5..max).to_a.delete_if(&:even?).each_with_object([2, 3]) do |e, a|
      limit = Math.sqrt(e).round
      lst = a.take_while { |i| i < limit }
      a.push e unless lst.any? { |i| e % i == 0 }
    end
    res.count
  end

  def eratostenes
    max = 199_999
    lst = (2..max).to_a
    result = []
    sqrt = Math.sqrt(max)

    loop do
      elem = lst.shift
      result << elem
      break if elem >= sqrt
      lst.delete_if { |i| i % elem == 0 }
    end

    (result + lst).count
  end

  def prime
    require 'prime'
    max = 199_999
    Prime.each(max).count
  end

  x.config(time: 10, warmup: 2)
  x.report('calc') { calc }
  x.report('eratostenes') { eratostenes }
  x.report('prime') { prime }
  x.compare!
end

Warming up --------------------------------------
                calc     1.000  i/100ms
         eratostenes     1.000  i/100ms
               prime    21.000  i/100ms
Calculating -------------------------------------
                calc      0.596  (± 0.0%) i/s -      6.000
         eratostenes      4.838  (±20.7%) i/s -     46.000
               prime    195.376  (±21.5%) i/s -      1.848k

Comparison:
               prime:      195.4 i/s
         eratostenes:        4.8 i/s - 40.39x slower
                calc:        0.6 i/s - 327.62x slower

Prime早い…エラトステネスの篩も最初のやり方に比べたらかなり早いですね。Primeどうやっているんだろう。

Comments