Submission #2792189


Source Code Expand

Copy
# coding: utf-8

def erastosthenes_table(n)
  # 0,1は素数(false)
  checked = Array.new(n+1,false)
  is_prime = Array.new(n+1,true)

  is_prime[0] = false
  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

  is_prime
end

$pn_table = erastosthenes_table(10**5+1)
$table = Array.new(10**5+1,0)

def is_prime?(n)
  $pn_table[n]
end

def like_2017?(n)
  is_prime?(n) and is_prime?((n+1)/2)
end

1.step(10**5,1).each do |e|
  if like_2017?(e) and e.odd?
    $table[e] = $table[e-1] + 1
  else
    $table[e] = $table[e-1]
  end
end

#lines = <<'EOS'
#6
#1 53
#13 91
#37 55
#19 51
#73 91
#13 49
#EOS
lines = $stdin.read
array = lines.split("\n")

Q = array[0].to_i

array[1..Q].each do |str|
  l,r = str.split(" ").map(&:to_i)
  puts $table[r] - $table[l-1]
end

Submission Info

Submission Time
Task D - 2017-like Number
User hiroyuking
Language Ruby (2.3.3)
Score 400
Code Size 999 Byte
Status
Exec Time 303 ms
Memory 12652 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 303 ms 12652 KB
02.txt 295 ms 12652 KB
03.txt 295 ms 12652 KB
04.txt 294 ms 12652 KB
05.txt 295 ms 12268 KB
06.txt 294 ms 12396 KB
07.txt 297 ms 12524 KB
sample_01.txt 58 ms 4092 KB
sample_02.txt 58 ms 4092 KB
sample_03.txt 59 ms 4092 KB