Skip to content

Instantly share code, notes, and snippets.

@whatalnk whatalnk/abc084-d.rb
Created Sep 28, 2018

Embed
What would you like to do?
AtCoder ABC #084 D 2017-like Number
require 'prime'
Q_MAX = 10**5
pm = Array.new(Q_MAX + 2, false)
Prime.each(Q_MAX+1) do |n|
pm[n] = true
end
like2017 = Array.new(Q_MAX + 2, 0)
(Q_MAX+1).times do |i|
if i.odd? && pm[i] && pm[(i+1)/2]
like2017[i] = 1
end
end
(Q_MAX + 1).times do |i|
like2017[i+1] += like2017[i]
end
q = gets.chomp.to_i
q.times do
l, r = gets.chomp.split(" ").map(&:to_i)
puts like2017[r] - like2017[l-1]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.