# AtCoder Beginner Contest 084

URL: https://atcoder.jp/contests/abc084 (opens new window)

# D

require "set"
q = gets.chomp.to_i
lr_arr = q.times.map{gets.chomp.split(" ").map(&:to_i)}

MAX = 10 ** 5
set = Set.new((2..MAX))

# 10 ** 5までの素数を求める
2.upto(Math.sqrt(MAX)).each do |i|
  tmp = i
  while tmp <= MAX do
    tmp += i
    set.delete(tmp)
  end
end

# 累積
arr = [0]
1.upto(MAX) do |i|
  if set.include?(i) && set.include?((i+1)/2)
    arr[i] = arr[i-1] + 1
  else
    arr[i] = arr[i-1] 
  end
end

lr_arr.each do |(l, r)|
  puts arr[r] - arr[l-1]
end
Last Updated: 2020/08/10 21:46