🐢

[鉄則A26] Prime Check

2024/05/13に公開

Ruby

素数判定問題。

問題を要約する

X は素数か？

単純な実装 (TLE)

Q = gets.to_i                            # => 4
X = Q.times.collect { gets.to_i }        # => [17, 31, 35, 49]

ans = X.collect do |x|
  range = 2..x.pred                      # => 2..16, 2..30, 2..34, 2..48
  range.none? { |d| x.modulo(d).zero? }  # => true, true, false, false
end
puts ans.collect { |e| e ? "Yes" : "No" }

2 から X - 1 までの整数で割り切れるものがなければ素数とする方法は遅い。

効率的な実装 (AC)

264 ms

Q = gets.to_i                            # => 4
X = Q.times.collect { gets.to_i }        # => [17, 31, 35, 49]

ans = X.collect do |x|
  range = 2..Integer.sqrt(x)             # => 2..4, 2..5, 2..5, 2..7
  range.none? { |d| x.modulo(d).zero? }  # => true, true, false, false
end
puts ans.collect { |e| e ? "Yes" : "No" }

2 から √X 以下の整数で割り切れるものがなければ素数とする方法は一応 AC になる。

エラトステネスのふるい (AC)

138 ms

Q = gets.to_i                        # => 4
X = Q.times.collect { gets.to_i }    # => [17, 31, 35, 49]

MAX = X.max
invalid = Array.new(MAX.next)
(2..Integer.sqrt(MAX)).each do |e|
  unless invalid[e]             # ← これを忘れるな！
    (e * 2).step(by: e, to: MAX).each do |v|
      invalid[v] = e
    end
  end
end

ans = X.collect { |x| !invalid[x] }  # => [true, true, false, false]
puts ans.collect { |e| e ? "Yes" : "No" }

問題の制約には最大30万とあるため MAX = 300000 でもいいが、メモリ消費とマジックナンバーが気になるので MAX = X.max とした。効率が相殺されたようでトータルの実行時間に差はなかった。

組み込みライブラリを使う

101 ms

Q = gets.to_i                      # => 4
X = Q.times.collect { gets.to_i }  # => [17, 31, 35, 49]

require "prime"
ans = X.collect(&:prime?)          # => [true, true, false, false]
puts ans.collect { |e| e ? "Yes" : "No" }

単発で Integer#prime? で呼ぶのは遅いのではないかと考えて、最初に X.max.prime? を実行してみたが効果はなかった。