🐢
[鉄則A26] Prime Check
素数判定問題。
問題を要約する
- 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? を実行してみたが効果はなかった。
Discussion