Submission #2331023


Source Code Expand

Copy
N = 100000

checked = Array.new(N+1,false)
is_prime = Array.new(N+1,true)

is_prime[1] = false
for i in 2..(Math.sqrt(N).floor)
  next if checked[i]

  is_prime[i] = true
  checked[i] = true

  j = 2
  for j in 2..(N/i)
    checked[i*j] = true
    is_prime[i*j] = false
  end
end

like_2017 = Array.new(N+1,0)
for i in 1..N
  if is_prime[i] && is_prime[(i+1)/2]
    like_2017[i] = like_2017[i-1]+1
  else
    like_2017[i] = like_2017[i-1]    
  end
end

q = gets.chomp.to_i
q.times do
  l, r = gets.chomp.split(" ").map(&:to_i)
  puts like_2017[r] - like_2017[l-1]
end

Submission Info

Submission Time
Task D - 2017-like Number
User taka99
Language Ruby (2.3.3)
Score 400
Code Size 602 Byte
Status
Exec Time 337 ms
Memory 4604 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
01.txt 337 ms 4604 KB
02.txt 335 ms 4476 KB
03.txt 334 ms 4476 KB
04.txt 335 ms 4476 KB
05.txt 330 ms 4476 KB
06.txt 332 ms 4476 KB
07.txt 335 ms 4348 KB
sample_01.txt 52 ms 4092 KB
sample_02.txt 52 ms 4220 KB
sample_03.txt 52 ms 4092 KB