Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Wrong Answer

Solution code:
l=[0]*100001
def eratosthenes(n):
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
tmp=eratosthenes(100000)
tmp.sort(reverse=True)
for i in tmp:
   l[i]=1
tmp=tmp[1:]
for i in tmp:
   if l[(i+1)//2]==0:
      l[i]=0 
   else:
      pass
l[2]=0
l2=[0]*100001
s=0
X=int(input())
for i in range(1,100000):
   s+=l[i]
   l2[i]=s
for i in range(X):
   x,y=list(map(int,input().split()))
   print(l2[y]-l2[x-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

def sPN(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

p = sPN(100000)

import bisect

for i in range(n):
    temp = bisect.bisect(p,ab[i][1])-bisect.bisect(p,ab[i][0])
    if ab[i][0] in p:
        temp +=1
    print(temp)

Submission status: Wrong Answer

Solution code:
def calc_prime(n):
    primes = set(list(range(3, n, 2)))
    primes.add(2)
    for a in range(3, n, 2):
        for i in range(a, n):
            x = a * i
            if x >= n:
                break
            if x in primes:
                primes.remove(x)

    return primes


def collect_likes(ps):
    likes = set([p for p in ps if (p + 1) / 2 in ps])
    return likes


def line(xs, n):
    ps = list(xs)
    ps.sort()
    cs = [0] * n
    p0 = 0
    s = 0
    for p in ps:
        for i in range(p0, p + 1):
            cs[i] = s

        p0 = p
        s += 1

    return cs


def main():
    n = 10 ** 5
    primes = calc_prime(n)
    likes = collect_likes(primes)
    cums = line(likes, n)
    #print(sorted(list(primes))[:100])
    #print(sorted(list(likes))[:100])
    #print(cums[:10])

    q = int(input())
    for _ in range(q):
        l, r = [int(x) for x in input().split()]
        ans = cums[r] - cums[l]
        if l in likes:
            ans += 1

        print(ans)


main()

Submission status: Wrong Answer

Solution code:
q = int(input())
LR = [0]*q
for i in range(q):
    LR[i] = list(map(int,input().split()))
lis = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173]

p_lis = [0]*(1+10**5)
for i in range(3,10**5+1):
    sw1 = 1
    sw2 = 1
    for P in lis:
        if P > i**0.5:
            break
        if i%P == 0:
            sw1 = 0
            break
        
    if sw1 == 1:
        for P in lis:
            if P > ((i+1)//2)**0.5:
                break
            if (i+1)//2%P == 0:
                sw2 = 0
                break
            
    if sw1 == 1 and sw2 == 1:
        p_lis[i] = 1
s_lis = [0]*(1+10**5)
for i in range(1,len(p_lis)):
    if p_lis[i] == 1:
        s_lis[i] = s_lis[i-1] + 1
    else:
        s_lis[i] = s_lis[i-1]
for L,R in LR:
    print(s_lis[R]-s_lis[L-1])

Submission status: Wrong Answer

Solution code:
def main():
    import math
    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set([p for p in primes if p != 0])

    primes = generate_primes(100000)
    ans = [0] * 50000
    for j in range(1, 50000):
        i = 2 * j + 1
        if i in primes and (i + 1) / 2 in primes:
            ans[j] = ans[j - 1] + 1
        else:
            ans[j] = ans[j - 1]
    q = int(input())
    for _ in range(q):
        l, r = list(map(lambda x: (int(x) - 1) // 2, input().split()))
        print(ans[r] - ans[l - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

s = [0]
for i in range(10**5+1): #s[i]: iがokなら1
    if i%2 == 1 and is_prime(i) and is_prime((i+1)//2):
        s.append(1)
    else:
        s.append(0)

lst = [0]
for i in range(10**5):
    lst.append(lst[i]+s[i+1])

q = int(input())
for k in range(q):
    l, r = map(int, input().split())
    print(lst[r]-lst[l-1])

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    # エラトステネスの篩で、
    # 2 から 10^5までの素数を列挙
    limit = 10 ** 5 + 1
    prime = [False if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 else True for n in range(limit)]
    prime[0] = prime[1] = False
    prime[2] = prime[3] = prime[5] = True
    for p in range(3, limit, 2):
        if math.sqrt(limit) < p:
            break
        for q in range(p ** 2, limit, p):
            prime[q] = False

    # 累積和
    # 2017に似た数字の数を求めておく
    cnt = [0]*limit
    for n in range(len(cnt)):
        if prime[n] and prime[(n+1)//2]:
            cnt[n] = 1
    for n in range(1, len(cnt)):
        cnt[n] += cnt[n-1]

    # 回答
    Q = ii()
    for q in range(Q):
        l, r = il()
        print(cnt[r-1]-cnt[l-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
MAX = 10**5
N = [0]*MAX

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

n = int(input())
sosuu = eratosthenes((MAX+1)//2)

total = 0
mae = sosuu[0]
for s in sosuu:
    for i in range(mae,s):
        N[i] = total
    if (s+1) // 2 in sosuu:
        total += 1
    mae = s

for i in range(n):
    l,r = map(int,input().split())
    print(N[r]-N[l-1])

Submission status: Wrong Answer

Solution code:
#ABC084D
def main():
    import sys
    N = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #print(LR)
    
    #エラのふるい
    L = [i for i in range(2, 10**5+1)]
    def era(L):
        import math
        for i in range(int(math.sqrt(10**5))):
            for j in range(len(L)-1, i, -1):
                if L[j] % L[i] ==0:
                    L.pop(j)
        return L
    
    L = era(L)
    M = list(map(lambda x:(x+1)//2, L))
    M = era(M[1:])
    L = list(map(lambda x:x*2-1, M))
    #print(L)
    #累積和
    R = [0 for _ in range(10**5+1)]
    j = 0
    for i in range(len(R)):
        if i ==L[j]:
            R[i] =R[i-1] +1
            j+=1
        else:
            R[i] = R[i-1]
        if j ==len(L):
            break
    #print(R)
    for lr in LR:
        print(R[lr[1]] - R[lr[0]-1])
        
    


if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

q = int(input())
plist = [2]
like2017 = []
n = 3
while n <= 10000:
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            break
    else:
        plist.append(n)
        if (n + 1) // 2 in plist:
            like2017.append(n)
    n += 2
for _ in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(like2017, r) - bisect.bisect_left(like2017, l))

Submission status: Wrong Answer

Solution code:
def l(): return list(map(int, input().split()))
def m(): return map(int, input().split())

# def sieve(n): # エラトステネスの篩ですよ
#   num = [True]*n
#   num[0] = num[1] = False
#   for i in range(2,int(n**0.5)+1):
#     if num[i]:
#       for j in range(i**2, n, i):
#         num[j] = False
#   return [i for i in range(2,n) if num[i]]

def main():
  q = int(input())
  l , r = [0]*q, [0]*q
  for i in range(q):
    l[i], r[i] = m()
  rr = max(r) 
  # prime = sieve(rr+1)
  MAX = 101010
  is_prime = [1]*MAX
  is_prime[0] = 0
  is_prime[1] = 0
  for i in range(2,MAX):
    if not is_prime[i]: 
      continue
    for j in range(i*2, MAX, i):
      is_prime[j] = 0
  prime = is_prime
  # print(prime)
  likp = [0]*rr
  for i in prime:
    if (i+1) // 2 in prime:
      likp[i-1] = 1
  # print(likp)
  sm = [0]*(rr+1)
  for i in range(rr):
    sm[i+1] = sm[i] + likp[i]
  # print(sm)
  for i in range(q):
    print(sm[r[i]] - sm[l[i]-1])

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def isprime(n):
  m = (n + 1) // 2
  i = 2

  if m in primedic and n in primedic:
    return True

  while i * i <= m:
    if m % i == 0:
      return False
    i += 1
  i -= 1
  while i * i <= n:
    if n % i == 0:
      return False
    i += 1
  return True
  
primedic = {}

Q = int(input())
for i in range(Q):
  l,r = map(int,input().split())
  ans = 0
  for i in range(l,r + 1):
    if isprime(i):
      primedic[i] = True
      primedic[(i + 1) // 2] = True
      ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
def isPrime(x):
    if x < 2:
        return False
    if x % 2 == 0:
        return False
    cur = 3
    while True:
        if cur * cur > x:
            break
        if x % cur == 0:
            return False
        cur += 2
    return True


Q = int(input())
num = [0] * 100010
for i in range(3,100001,2):
    if isPrime(i) and isPrime((i+1)//2):
        num[i] += 1
for i in range(0,100001):
    num[i+1] += num[i]


for _ in range(Q):
    l,r = map(int, input().split())
    print(num[r] - num[l-1])

Submission status: Wrong Answer

Solution code:

import bisect

n = 10**5
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    count = 0
    insert_index1 = bisect.bisect_left(simular_2017, l)
    insert_index2 = bisect.bisect_left(simular_2017, r)
    print(insert_index2 - insert_index1)

Submission status: Wrong Answer

Solution code:
import math
from itertools import accumulate

def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n))+1):
    if n % k == 0: return False
  return True

q=int(input())
r_max=10**5+1
A=[1 if is_prime(i)and is_prime((i + 1)//2) else 0 for i in range(r_max) ]
S=[0]+list(accumulate(A))

for i in range(q):
  l,r=list(map(int,input().split()))
  ans=S[r-1]-S[l-1]
  if l==1:ans-=1
#  if l<=2017<=r:ans+=1
  if l==r and is_prime(i) and is_prime((i + 1)//2):ans+=1
  print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import accumulate

def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n))+1):
    if n % k == 0: return False
  return True

q=int(input())
r_max=10**5+1
A=[1 if is_prime(i)and is_prime((i + 1)//2) else 0 for i in range(r_max) ]
S=[0]+list(accumulate(A))

for i in range(q):
  l,r=list(map(int,input().split()))
  print((S[r-1]-S[l-1]) if l!=1 else S[r-1]-S[l-1]-1)

Submission status: Wrong Answer

Solution code:
from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

ans = [0 for i in range(M)]
for i in range(1, M):
    ans[i] = ans[i-1] + a[i]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 1
    for i in range(2, l):
        if not isp[i]: continue
        for j in range(i*2, n, i): isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1
print(cnt[:10])
acc = list(accumulate(cnt))
for _ in range(q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 1
    for i in range(3, l):
        if not isp[i]: continue
        for j in range(i*2, n, i): isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

ans = 0
for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1
acc = list(accumulate(cnt))
for _ in range(q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 1
    i = 4
    while i < n+1:
        isp[i] = False
        i *= 2
    for i in range(3, l, 2):
        if not isp[i]:
            continue
        for j in range(i*2, n, i):
            isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

ans = 0
for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1
acc = list(accumulate(cnt))
for _ in range(q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = floor(sqrt(n))
    n += 1
    i = 4
    while i < n+1:
        isp[i] = False
        i *= 2
    for i in range(3, l, 2):
        if not isp[i]:
            continue
        for j in range(i*2, n, i):
            isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

ans = 0
for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        ans += 1
    cnt[i] = ans
for _ in range(q):
    l, r = map(int, input().split())
    print(cnt[r] - cnt[l-1])

Submission status: Wrong Answer

Solution code:
"""
10^5以下の素数を列挙しておく。
それをもとに、10^5以下の各整数以下の2017に似た数の個数のメモを作成する。
"""
#10^5以下の素数を列挙
prime = [1] * (100001)
prime[0] = 0
prime[1] = 0
for i in range(2,100001):
    if prime[i]:
        for j in range(i*i,100001,i):
            prime[j] = 0

memo = [0]*(100001)
for i in range(3,100001):
    memo[i] = memo[i-1]
    if prime[i]==1 and prime[(i+1)]:
        memo[i] += 1

Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    print(memo[r]-memo[l-1])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
INF = float('inf')


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
# これが素数
print(P)
P = [n for n in P if (n + 1) // 2 in P]
# 自身 + 1 //2 も素数であるもののみに絞る
print(P)
a = [0] * (N + 1)
for n in P:
    # likenumberは1にする
    a[n] = 1
# 累積和に変換
a = list(accumulate(a))


Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])

Submission status: Wrong Answer

Solution code:
Q = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]], is_prime

primes_num, is_primes = primes(10**5+5)
sums = [0]
cnt = 0

for i in range(0, 10**5+4):
    if i % 2 != 0:
        a = (i+1) // 2
        if is_primes[i] and is_primes[a]:
            cnt += 1

    sums.append(cnt)

for i in range(Q):
    l, r = map(int, input().split())
    if l == r:
        if is_primes[l]:
            print(1)
        else:
            print(0)
    else:
        print(sums[r]-sums[l])

Submission status: Wrong Answer

Solution code:
#素数判定
import math
from itertools import accumulate
def sosuu(n):
  if n==2:
    return True
  else:
    for i in range(2,int(math.sqrt(n)+1)):
      if n%i==0:
        return False
    return True

#入力
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=list(map(int,input().split()))
L=min(l)
R=max(r)

#累積和を作る
A=[]
for i in range(L,R+1):
    if sosuu(i) and sosuu(int((i+1)/2)):
        A.append(1)
    else:
        A.append(0)
s=[0]+A
S=list(accumulate(s))
for i in range(q):
    #print(S[r[i]-L+1])
    #print(S[l[i]-L])
    print(S[r[i]-L+1]-S[l[i]-L])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = [0] * (N + 1)
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[(i + 1) >> 1]:
                    like2017[i] = 1
            return like2017
        if numbers[(p + 1) >> 1]:
            like2017[p] = 1
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
like2017_sum = list(accumulate(like2017))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(like2017_sum[r] - like2017_sum[l] + like2017[l])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = []
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[(i + 1) >> 1]:
                    like2017.append(i)
            return like2017
        if numbers[(p + 1) >> 1]:
            like2017.append(p)
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    lindex = bisect_left(like2017, l)
    rindex = bisect(like2017, r)
    print(rindex - lindex)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = []
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if numbers[(p + 1) >> 1]:
            like2017.append(p)
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[(i + 1) >> 1]:
                    like2017.append(i)
            return like2017
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    lindex = bisect_left(like2017, l)
    rindex = bisect(like2017, r)
    print(rindex - lindex)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = []
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if numbers[(p + 1) >> 1]:
            like2017.append(p)
        if p * p > N:
            for i in range(p, N + 1, 2):
                if numbers[(i + 1) >> 1]:
                    like2017.append(i)
            return like2017
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
print(like2017)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    lindex = bisect_left(like2017, l)
    rindex = bisect(like2017, r)
    print(rindex - lindex)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect
def sieve_of_eratosthenes_2017(N):
    numbers = [n & 1 for n in range(N + 1)]
    numbers[1] = 0
    numbers[2] = 1
    like2017 = []
    p = 1
    while True:
        while not numbers[p]:
            p += 2
        if numbers[(p + 1) >> 1]:
            like2017.append(p)
        if p * p > N:
            for i in range(p, N + 1, 2):
                if (i + 1) >> 1:
                    like2017.append(i)
            return like2017
        for i in range(p * 2, N + 1, p):
            numbers[i] = 0
        p += 2

like2017 = sieve_of_eratosthenes_2017(10 ** 5)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    lindex = bisect_left(like2017, l)
    rindex = bisect(like2017, r)
    print(rindex - lindex)

Submission status: Wrong Answer

Solution code:
def eratosthenes(limit):
    import math
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > math.sqrt(limit): break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A: P.append(a)
    return P
l = eratosthenes(10**5)
ans = [0]*(10**5+1)
d = [0]*(10**5+1)
for i in l: d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Submission status: Wrong Answer

Solution code:
Q = int(input())
import numpy as np

n = 10 ** 5
doubel_primes = np.zeros(n+1, dtype=int)
primes_flags = np.zeros(n+1, dtype=bool)
primes_flags[1] = True # Trueはprimeでない.
primes_flags[0] = True # Trueはprimeでない.
#primes_flags[2] = True # Trueはprimeでない.
primes_flags[::2] = True # Trueはprimeでない.
if Q >= 2:
    primes_flags[2] = False
def prime_check(n=100000):
    i = 3
    while i  < n:
        if not primes_flags[i]:
            if not primes_flags[i//2 + 1]:
                doubel_primes[i] = 1
            k = i * i
            while k <= n:
                primes_flags[k] = True
                k += i
        i += 2
        
prime_check(n)
prime_sum = doubel_primes.cumsum()
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(prime_sum[r] - prime_sum[l-1])

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
q = int(input())
a = [0 for i in range(10 ** 5)]
for i in range(10 ** 5):
    if (i + 1) % 2 == 1 and is_prime(i + 1) and is_prime((i + 2) // 2):
        a[i] = 1
for i in range(1, 10 ** 5):
    a[i] += a[i - 1]
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(a[r] - a[l - 1])