🐢
[鉄則B26] Output Prime Numbers
N 以下の素数を求める問題。
要点
- N 以下なので「N まで」をエラトステネスのふるいで用意する
- 0 と 1 は素数に含まない
- 組み込みライブラリでは専用メソッドを使う
エラトステネスのふるいを使う場合 (AC)
394 ms
N = gets.to_i # => 20
invalid = Array.new(N.next)
(2..Integer.sqrt(N)).each do |e|
unless invalid[e]
(e * 2).step(by: e, to: N).each do |i|
invalid[i] ||= e
end
end
end
# 素数から 0, 1 を除外する
invalid[0] = true
invalid[1] = true
primes = []
invalid.each.with_index { |e, i| e or primes << i }
primes # => [2, 3, 5, 7, 11, 13, 17, 19]
puts primes
組み込みライブラリを使う場合 (AC)
196 ms
require "prime"
N = gets.to_i
primes = Integer.each_prime(N).to_a # => [2, 3, 5, 7, 11, 13, 17, 19]
puts primes
連続で求める場合は Integer.each_prime を使う。
まちがった使い方 (TLE)
require "prime"
N = gets.to_i
primes = []
N.next.times { |i| i.prime? and primes << i }
primes # => [2, 3, 5, 7, 11, 13, 17, 19]
puts primes
ひとつずつ Integer#prime? で判定すると TLE になる。
Discussion