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:
# Python program to print all primes smaller than or equal to 
# n using Sieve of Eratosthenes 
  
def SieveOfEratosthenes(n):
    # copy pasted from https://www.geeksforgeeks.org/sieve-of-eratosthenes/
      
    # Create a boolean array "prime[0..n]" and initialize 
    #  all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
      
    # Print all prime numbers 
    ans = []
    for p in range(2, n): 
        if prime[p]: 
            ans.append(p)
    return ans

def binarySearch (arr, l, r, x): 
    # from https://www.geeksforgeeks.org/python-program-for-binary-search/
    # Check base case 
    if r >= l: 
  
        mid = int(l + (r - l)/2)
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return True 
          
        # If element is smaller than mid, then it can only 
        # be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present in right subarray 
        else: 
            return binarySearch(arr, mid+1, r, x) 
  
    else: 
        # Element is not present in the array 
        return False
  
# Test array 

primes = SieveOfEratosthenes(10**5+9)
sheet = []
for x in range(1, 10**5+9):
  sheet.append(binarySearch(primes, 0, len(primes)-1, x) and binarySearch(primes, 0, len(primes)-1, (x+1)/2))
counts = []
count = 0
for x in sheet:
  if x:
    count += 1
    counts.append(count)
  else:
    counts.append(count)
x = 2
print(primes[x])
print(sheet[x])
print(counts[x])

"""
queries = int(input())
for j in range(queries):
  a,b = [int(x) for x in input().split()]
  ans.append(sheet[a-1:b].count(True))
  """

Submission status: Wrong Answer

Solution code:
Q = int(input())
ans = 0
INF = 10 ** 5
is_prime = [1] * INF
rui = [0] * (INF + 1)
def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

eratorasu()
sosu = [0] * INF
for i in range(INF):
    if is_prime[i] == 1 and is_prime[(i + 1) // 2] == 1:
        sosu[i] = 1

rui = [0] * (INF + 1)
for i in range(INF):
    rui[i + 1] = rui[i] + sosu[i]

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

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def searchPrimeNumber(N):
    N = N + 1
    is_prime = np.ones(N, dtype=bool)
    is_prime[:2] = 0
    N_max = int(np.sqrt(N))
    for j in range(2, N_max+1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    prime = np.arange(N)[is_prime]
    return prime


def main():
    Q = int(readline())
    m = map(int, read().split())
    LR = list(zip(m, m))
    A = searchPrimeNumber(10**5)
    B = np.zeros(10**5+1, dtype=np.int32)  # Bはゼロ始まり
    for a in A:
        if (a + 1) / 2 in A:
            B[a+2:] += 1  # like 2017の数より１つ大きい数から1増やす

    for l, r in LR:
        c = B[r+1] - B[l+1]
        if c != 0:
            print(c)
        else:
            if r == l:
                if r in A:
                    print(1)
                else:
                    print(0)
            else:
                print(0)



main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def searchPrimeNumber(N):
    N = N + 1
    is_prime = np.ones(N, dtype=bool)
    is_prime[:2] = 0
    N_max = int(np.sqrt(N))
    for j in range(2, N_max+1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    prime = np.arange(N)[is_prime]
    return prime


def main():
    Q = int(readline())
    m = map(int, read().split())
    LR = list(zip(m, m))
    A = searchPrimeNumber(10**5)
    B = np.zeros(10**5+1, dtype=np.int32)
    for a in A:
        if (a + 1) / 2 in A:
            B[a+1:] += 1

    for l, r in LR:
        c = B[r] - B[l]
        if c != 0:
            print(c)
        else:
            if r == l:
                if r in A:
                    print(1)
                else:
                    print(0)
            else:
                print(0)



main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def searchPrimeNumber(N):
    N = N + 1
    is_prime = np.ones(N, dtype=bool)
    is_prime[:2] = 0
    N_max = int(np.sqrt(N))
    for j in range(2, N_max+1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    prime = np.arange(N)[is_prime]
    return prime


def main():
    Q = int(readline())
    m = map(int, read().split())
    LR = list(zip(m, m))
    # 事前に10**5までにある2017に似た素数リストを作る
    A = searchPrimeNumber(10**5)

    B = np.zeros(10**5+1, dtype=np.int32)
    cnt = 0
    l = 0
    for a in A:
        if (a + 1) / 2 in A:
            cnt += 1
            B[l:a+1] = cnt
            l = a+1

    for l, r in LR:
        c = B[r] - B[l]
        if c != 0:
            print(c)
        else:
            if r == l:
                if r in A:
                    print(1)
                else:
                    print(0)
            else:
                print(0)



main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def searchPrimeNumber(N):
    N = N + 1
    is_prime = np.ones((N,), dtype=bool)
    is_prime[:2] = 0
    N_max = int(np.sqrt(N))
    for j in range(2, N_max+1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    prime = np.arange(N)[is_prime]
    return prime


def main():
    Q = int(readline())
    m = map(int, read().split())
    LR = list(zip(m, m))
    A = searchPrimeNumber(10**5)

    like_2017 = np.zeros(10**5 + 1, dtype=bool)
    for a in A:
        if (a + 1) / 2 in A:
            like_2017[a] = True

    B = np.arange(10**5+1)[like_2017]
    for l, r in LR:
        print(B[(l <= B) & (B <= r)])


main()

Submission status: Wrong Answer

Solution code:
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  h=0
  ans=0
  for j in range(a,b+1):
    for v in range(2,round(j**0.5)):
      if j%v==0:
        h+=1
    if h==0:
      for k in range(2,round(((j+1)/2)**0.5)):
        if ((j+1)//2)%k==0:
          h+=1
    if h==0:
      ans+=1
    h=0      
  print(ans)

Submission status: Wrong Answer

Solution code:
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  h=0
  ans=0
  for j in range(a,b+1):
    for v in range(2,round(j**0.5)):
      if j%v==0:
        h+=1
    if h==0:
      for k in range(2,round(((j+1)/2)**0.5)):
        if ((j+1)//2)%k==0:
          h+=1
    if h==0:
      ans+=1
      
  h=0
      
  print(ans)

Submission status: Wrong Answer

Solution code:
def solve(num):
    ans = pow(2, num-1, num)
    ANS = pow(2, (num+1)//2 -1, (num+1)//2)
    if num == 2:
        ans = 1
    if (num+1)//2 == 2:
        ANS = 1
    if num < 2 or num == 1 or (num+1)//2 == 1:
        ans = 10**9
    if ans == 1 and ANS == 1:
        return 1
    else:
        return 0


def main():
    q = 10**5+1
    Q = int(input())
    dt = [0 for _ in range(q)]
    count = 0
    for i in range(1, q, 2):
        count += solve(i)
        dt[i] = count

    ddd= [list(map(int, input().split())) for _ in range(Q)]
    for l, r in ddd:
        print(dt[r]-dt[max(l-2, 1)])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

number = 10**5+1


q = int(input())
lr = [[int(i) for i in input().split()] for j in range(q)]

ans = [0]*(number)
tmp = False

for i in range(number):
    num = i*2+1
    if num >= number:
        break
    if is_prime(num) and is_prime((num+1)/2):
        ans[i] = 1
    else:
        ans[i] = 0

rui = [0]*(number)

#print(ans)

for i in range(1,number):
    rui[i] = rui[i-1] + ans[i-1]

#print(rui)

for i in range(q):
    if lr[i][1] == lr[i][0]:
        if rui[lr[i][1]//2+1] - rui[lr[i][1]//2] == 1:
            print(1)
        else:
            print(0)
        continue
    print(rui[lr[i][1]//2]-rui[lr[i][0]//2])

Submission status: Wrong Answer

Solution code:
q = int(input())
    
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

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)//2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    if l == r:
        if is_prime(l) and is_prime((l+1)//2):
            print(1)
        else:
            print(ls[r-1]-ls[l-1])  
    else:
        print(ls[r-1]-ls[l-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
    
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

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)//2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    if l == r:
        if is_prime(l) and is_prime((l+1)//2):
            print(1)
    else:
        print(ls[r-1]-ls[l-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
    
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

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)//2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    if l == r:
        if is_prime(l) and is_prime((l+1)/2):
            print(1)
    else:
        print(ls[r-1]-ls[l-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
    
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

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)/2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    print(ls[r-1]-ls[l-1])

Submission status: Wrong Answer

Solution code:
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  h=0
  for j in range(a,b+1):
    for v in range(2,j):
      if j%v==0:
        for k in range(2,round((j+1)/2)):
          if j%k==0:
            h+=1
          else:
            pass
      else:
        pass
      
  print(h)

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    # 素数判定
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1
def near2017(n):
    if is_prime(n):
        return is_prime((n+1)//2)
    else:
        return False
#############################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = 1000000
prime = [0]*1000001
cur = 0
ans = []
for i in range(1,N+1):
    if near2017(i):
        cur +=1
        prime[i] = cur
    else:
        prime[i] = prime[i-1]
#print(prime)

Q = I()
for i in range(Q):
    l, r = LI()
    cur = prime[r] - prime[l-1]
    ans.append(cur)

for v in ans:
    print(v)

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    # 素数判定
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1
def near2017(n):
    if is_prime(n):
        return is_prime((n+1)//2)
    else:
        return False
#############################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = 100000
prime = [0]*100001
cur = 0
ans = []
for i in range(1,N+1):
    if near2017(i):
        cur +=1
        prime[i] = cur
    else:
        prime[i] = prime[i-1]
#print(prime)

Q = I()
for i in range(Q):
    l, r = LI()
    cur = prime[r] - prime[l-1]
    ans.append(cur)

for v in ans:
    print(v)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

S = str(input())
N = len(S)
ans = int(0)

k = N

for i in range(N-1):
    if S[i]!=S[i+1]:
        k = min(max(i+1,N-1-i),k)
ans = k
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def like_2017(n):
    if n == 1: return False
    if n == 2: return False 

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

q = int(input())
L = [[int(i) for i in input().split()] for _ in range(q)]
ans = [0 for _ in range(10**5+1)]

for i in range(3,10**5):
    ans[i+1] = ans[i] + 1 if like_2017(i) else ans[i] 

for l,r in L:
    print(ans[r] - ans[l])

Submission status: Wrong Answer

Solution code:

import math
def like_2017(n):
    if n == 1: return False

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

q = int(input())
L = [[int(i) for i in input().split()] for _ in range(q)]

for l,r in L:
    length = [i for i in range(l,r+1) if i % 2 == 1 and like_2017(i)]
    print(length,len(length))

Submission status: Wrong Answer

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

q = int(input())
ans = []

for j in range(q):
    cnt = 0
    l,r = map(int,input().split())
    for k in range(l,r+1):
        if k%2!=0 and isprime(k) and isprime((k+1)/2):
            cnt += 1
    ans.append(cnt)

print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
# D
import math
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    cand = []
    for m in range(l, r+1):
        if isPrime(m):
            cand.append((m+1)//2)
    total = 0
    for c in cand:
        if isPrime(c):
            total += 1
    print(total)

Submission status: Wrong Answer

Solution code:
def prime(n):
  if n==1:
    return False
  elif n==2:
    return True
  else:
    for i in range(2,int((n)**(1/2))+1):
      if n%i==0:
        return False
    return True
list=[True]*100001
for i in range(1,100001):
  if not prime(i):
    list[i]=False
list1=[0]
count=0
for i in range(1,100001):
  if i%2==1:
    if list[i] and list[(i+1)//2]:
      count+=1
  list1.append(count)
n=int(input())
for i in range(n):
  a,b=map(int,input().split())
  print(list1[b]-list1[a])

Submission status: Wrong Answer

Solution code:
Q = int(input())
L = [0]*Q
R = [0]*Q
for i in range(Q):
    L[i], R[i] = map(int, input().split())
    
N = 10**5+1
prime = [1]*N
prime[0] = 0
prime[1] = 0
for i in range(2, N):
    if prime[i] == 1:
        j = 2*i
        while j < N:
            prime[j] = 0
            j += i

S = [0]*N
i = 3
temp = 0
while i < N:
    if i%2 == 1 and 2*i-1 < N:
        if prime[i] == 1 and prime[(i+1)//2] == 1:
            temp += 1
    S[i] = temp
    i += 1
    
for i in range(Q):
    print(S[R[i]]-S[L[i]-1])

Submission status: Wrong Answer

Solution code:
Q = int(input())
L = [0]*Q
R = [0]*Q
for i in range(Q):
    L[i], R[i] = map(int, input().split())
    
N = 10**5+1
prime = [1]*N
prime[0] = 0
prime[1] = 0
for i in range(2, N):
    if prime[i] == 1:
        j = 2*i
        while j < N:
            prime[j] = 0
            j += i

S = [0]*N
i = 3
temp = 0
while 2*i-1 < N:
    if i%2 == 1:
        if prime[i] == 1 and prime[(i+1)//2] == 1:
            temp += 1
    S[i] = temp
    i += 1
    
for i in range(Q):
    print(S[R[i]]-S[L[i]-1])

Submission status: Wrong Answer

Solution code:
from math import sqrt
# エラトステネスのふるい
def sieve(n):
  if n <2:
    return [False]*(n)
  is_prime = [True]*(n)
  is_prime[0], is_prime[1] = False, False
  for i in range(2, int(sqrt(MAX))):
    if is_prime[i]:
      for j in range(i*2, n, i):
        is_prime[j] = False
  return is_prime
    
# 2017-like 数かどうか
MAX = 10**5
is_prime = sieve(MAX)
a = [0]*(MAX)
for i in range(MAX):
  if i%2 == 0:
    continue
  if is_prime[i] and is_prime[(i+1)//2]:
    a[i] = 1

#  累積和
s = [0]*(MAX+1)
for i in range(MAX):
  s[i+1] = s[i] + a[i]
  
# クエリ処理
Q = int(input())
for q in range(Q):
  l, r = map(int, input().split())
  print(s[r] - s[l])

Submission status: Wrong Answer

Solution code:
q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0 for i in range(672)]
#素数のリスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5*10**4:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        count+=1
        s[count-1]=[primes[i],count]
a=0
b=0

for i in range(q):
    for j in range(len(s)):
        if s[j][0]>=x[i][0]:
            a=s[j][1]
            break
    for j in range(len(s)):
        if s[j][0]>x[i][1]:
            b=s[j][1]
            break
    if a==0:
        a=672
    if b==0:
        b=673
    print(b-a)
    a=b=0

Submission status: Wrong Answer

Solution code:
q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0 for i in range(672)]
#素数のリスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5*10**4:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        count+=1
        s[count-1]=[primes[i],count]
a=0
b=0

for i in range(q):
    for j in range(len(s)):
        if s[j][0]>=x[i][0]:
            a=s[j][1]
            break
    for j in range(len(s)):
        if s[j][0]>x[i][1]:
            b=s[j][1]-1
            break
    if a==0:
        a=672
    if b==0:
        b=672
    print(b-a+1)
    a=b=0

Submission status: Wrong Answer

Solution code:
q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0 for i in range(672)]
#素数のリスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5*10**4:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        count+=1
        s[count-1]=[primes[i],count]
a=0
b=0

for i in range(q):
    for j in range(len(s)):
        if s[j][0]>=x[i][0]:
            a=s[j][1]-1
            break
    for j in range(len(s)):
        if s[j][0]>x[i][1]:
            b=s[j][1]-1
            break
    if b==0:
        b=672
    print(b-a)
    a=b=0

Submission status: Wrong Answer

Solution code:
q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0 for i in range(672)]
#素数のリスト
n = 100000
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>50000:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        count+=1
        s[count-1]=[primes[i],count]

a=0
b=0

for i in range(q):
    for j in range(len(s)):
        if s[j][0]>=x[i][0]:
            a=s[j][1]-1
            break
    for j in range(len(s)):
        if s[j][0]>x[i][1]:
            b=s[j][1]-1
            break
    print(b-a)
    a=b=0

Submission status: Wrong Answer

Solution code:
q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0 for i in range(109)]
#素数のリスト
n = 10000
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5000:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        count+=1
        s[count-1]=[primes[i],count]

a=0
b=0

for i in range(q):
    for j in range(len(s)):
        if s[j][0]>=x[i][0]:
            a=s[j][1]-1
            break
    for j in range(len(s)):
        if s[j][0]>x[i][1]:
            b=s[j][1]-1
            break
    print(b-a)
    a=b=0

Submission status: Wrong Answer

Solution code:
def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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]]

prime_number=prime(10**5)
number=[i for i in prime_number if (i+1)//2 in prime_number]+[0]
ans=[0]*(10**5+1)
count=0

for i in range(1,10**5):
    ans[i]=ans[i-1]
    if i==number[count]:
        ans[i] +=1
        count +=1

for i in range(int(input())):
    a,b=map(int,input().split())
    print(ans[b]-ans[a])

Submission status: Wrong Answer

Solution code:
Q = int(input())
que = []
for q in range(Q): que.append([int(i) for i in input().split()])

def Eratosthenes(n):
    li = [i for i in range(2,n+1)]
    judge = [True for i in range(n+1)]
    ans = []

    for i in range(2,n+1):
        if judge[i] == True:
            for j in range(i*2,n+1,i):
                judge[j] = False
            ans.append(i)
    judge[0],judge[1] = False,False
    return judge

judge = Eratosthenes(10**5)
tmp,ans = 0,[]
for i in range(10**5+1):
    if judge[i]==True and judge[int((i+1)/2)]: tmp+=1
    ans.append(tmp)

for q in que:
    l,r = q
    if l == r and judge[l]==True and judge[int((l+1)/2)]: print(1)
    else:
        tmp = ans[r]-ans[l]
        if (judge[l]==True and judge[int((l+1)/2)]) or (judge[r]==True and judge[int((r+1)/2)]):
            tmp += 1
        print(tmp)
    #print(ans[r],ans[l])

Submission status: Wrong Answer

Solution code:
Q = int(input())
que = []
for q in range(Q): que.append([int(i) for i in input().split()])

def Eratosthenes(n):
    li = [i for i in range(2,n+1)]
    judge = [True for i in range(n+1)]
    ans = []

    for i in range(2,n+1):
        if judge[i] == True:
            for j in range(i*2,n+1,i):
                judge[j] = False
            ans.append(i)
    judge[0],judge[1] = False,False
    return judge

judge = Eratosthenes(10**5)
tmp,ans = 0,[]
for i in range(10**5+1):
    if judge[i]==True and judge[int((i+1)/2)]:
        ans.append(tmp)
        tmp+=1
    else: ans.append(tmp)
#print(ans[:10])

for q in que:
    l,r = q
    if l == r and judge[l]==True and judge[int((l+1)/2)]: print(1)
    else: print(ans[r]-ans[l])
    #print(ans[r],ans[l])

Submission status: Wrong Answer

Solution code:
import math


def sieve_of_eratosthenes(N):
    target_list = list(range(2, N+1))
    sqrt_N = math.sqrt(N)
    prime_list = []

    while True:
        min_ = min(target_list)
        if min_ >= sqrt_N:
            prime_list.extend(target_list)
            break
        prime_list.append(min_)
        tmp_list = []
        for i in range(len(target_list)):
            if target_list[i] % min_ == 0:
                tmp_list.append(target_list[i])
        set_target = set(target_list) - set(tmp_list)
        target_list = list(set_target)

    return prime_list


Q = int(input())
prime_list = sieve_of_eratosthenes(10**5)
a_list = [0]*10**5
for i in range(1, 10**5, 2):
    if i in prime_list and (i + 1) / 2 in prime_list:
        a_list[i] = 1
ans = 0
for _ in range(Q):
    l, r = map(int, input().split())
    ans += sum(a_list[l:r+1])

Submission status: Wrong Answer

Solution code:
import math
import bisect


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    needed_prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return needed_prime + data
        prime.append(p)
        if int((p + 1) / 2) in prime and p != 2:
            needed_prime.append(p)
        data = [e for e in data if (e % p != 0)]


arr = get_sieve_of_eratosthenes(100000)


Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(arr, l)
    right_ind = bisect.bisect_right(arr, r)
    print(right_ind - left_ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

Q = int(input())

prime = {2, 3}
for i in range(5, 10 ** 5 + 1, 2) :
    flg = True
    for p in prime :
        if p * p > i :
            break
        if i % p == 0 :
            flg = False
            break
    if flg :
        prime.add(i)

like2017 = []
for p in prime :
    if (p + 1) // 2 in prime :
        like2017.append(p)
        
for _ in range(Q) :
    l, r = map(int, input().split())
    print(bisect_left(like2017, r + 1) - bisect_left(like2017, l))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())

LR = []
for _ in range(Q):
    l,r = map(int, input().split())
    LR.append((l,r))
    
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: True for i in range(n + 1) if is_prime[i]}

prime_dict = primes(10**5)
like_2017 = []
for n in prime_dict:
    if (n+1)//2 in prime_dict:
        like_2017.append(n)
#print(like_2017)


from bisect import bisect_left, bisect_right

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    return i

for l, r in LR:
    if l == r:
        if l in like_2017:
            print(1)
        else:
            print(0)
    else:
        l_idx = index(like_2017, l)
        r_idx = index(like_2017, r)
        if r in like_2017:
            r_idx += 1
        print(r_idx-l_idx)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())

LR = []
for _ in range(Q):
    l,r = map(int, input().split())
    LR.append((l,r))
    
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: True for i in range(n + 1) if is_prime[i]}

prime_dict = primes(10**5)
like_2017 = []
for n in prime_dict:
    if (n+1)//2 in prime_dict:
        like_2017.append(n)
#print(like_2017)


from bisect import bisect_left, bisect_right

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    return i

for l, r in LR:
    if l == r:
        if l in like_2017:
            print(1)
        else:
            print(0)
    else:
        l_idx = index(like_2017, l)
        r_idx = index(like_2017, r)
        print(r_idx-l_idx)

Submission status: Wrong Answer

Solution code:
import math
Q = int(input())

def sosuu(x):
  if x == 1:
    return False
  else:
    for i in range(2,int(math.sqrt(x))):
      if x % i == 0:
        return False
    return True

table=[0]*50001
for i in range(1,50001):
  if sosuu(2*i - 1) and sosuu(i):
    table[i]=table[i-1] + 1
  else:
    table[i]=table[i-1]
    
ans=[0]*Q
for i in range(Q):
  l,r=map(int,input().split())
  ans[i]=table[(r+1)//2] - table[(l+1)//2]
for i in range(Q):
  print(ans[i])