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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    m = II()
    print(48-m)
    return

#B
def B():
    a, _ = LI()
    s = S()
    ans = list(map(str, range(10)))
    for num, si in enumerate(s):
        if num != a:
            if si in ans:
                continue
            print("No")
            return
        else:
            if si == "-":
                continue
            print("No")
            return
    print("Yes")
    return

#C
def C():
    n = II()
    csf = LIR(n - 1)
    for i in range(n - 1):
        b = 0
        for k in range(i, n - 1):
            c, s, f = csf[k]
            if b <= s:
                b = s + c
            else:
                b += c + (-b % f)
        print(b)
    print(0)
    return

#D
def D_():
    a = II()
    ans = inf
    b = 0
    for _ in range(1, 10 ** 5):
        b += a
        ans = min(ans, sum(list(map(int, list(str(b))))))
    print(ans)
    return

def D():
    q = II()
    def primes(n):
        """ Input n>=6, Returns a list of primes, 2 <= p < n """
        """ 6以上の数であれば p (素数) <= n のlistを返す """
        n, correction = n-n%6+6, 2-(n%6>1)
        sieve = [True] * (n//3)
        for i in range(1,int(n**0.5)//3+1):
            if sieve[i]:
                k=3*i+1|1
                sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
                sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
        return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
    primelis = primes(10 ** 5)
    d = defaultdict(int)
    for i in primelis:
        d[i] += 1
    dp = [0]
    for i in range(3, 10 ** 5, 2):
        dp.append(dp[-1] + (1 if (d[i] and d[(i + 1) // 2]) else 0))
    for i in range(q):
        l, r = map(lambda x: x // 2, LI())
        if l == 0:
            print(r)
            continue
        print(dp[r] - dp[l - 1])



#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
import math


def sosu(N):
    tbl = [0] * (N + 1)
    tbl[0] = 1
    tbl[1] = 0
    lim = math.ceil(math.sqrt(N))
    for i in range(2, lim + 1):
        if tbl[i] == 0:
            for j in range(2, N + 1):
                tmp = i * j
                if tmp > N: break
                tbl[tmp] = 1
    return [i for i, v in [(i, v) for i, v in enumerate(tbl)] if v == 0]


pvals = sosu(10 ** 5)


def judge(N):
    return N in pvals and (N+1) // 2 in pvals


for _ in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    cnt = 0
    for i in range(l, r + 1, 2):
        cnt += int(judge(i))
    print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
  from math import sqrt
  readline = stdin.readline
  p = [True] * (10 ** 5 + 1)
  p[0] = False
  p[1] = False
  n = int(sqrt(10 ** 5 + 1)) + 1
  for j in range(4, n + 1, 2):
    p[j] = False
  for i in range(3, n + 1, 2):
    if p[i]:
      for j in range(i + i, n + 1, i):
        p[j] = False
  c = [0] * (10 ** 5 + 2)
  for i in range(2, 10 ** 5 + 2):
    c[i] = c[i - 1]
    if p[i - 2] and p[(i - 1) // 2]:
      c[i] += 1
  q = int(readline())
  for _ in range(q):
    l, r = map(int, readline().split())
    print(c[r + 2] - c[l + 1])
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
  from math import sqrt
  readline = stdin.readline
  p = [True] * (10 ** 5 + 1)
  p[0] = False
  p[1] = False
  n = int(sqrt(10 ** 5 + 1)) + 1
  for j in range(4, n, 2):
    p[j] = False
  for i in range(3, n, 2):
    if p[i]:
      for j in range(i + i, n, i):
        p[j] = False
  c = [0] * (10 ** 5 + 2)
  for i in range(2, 10 ** 5 + 2):
    c[i] = c[i - 1]
    if p[i - 2] and p[(i - 1) // 2]:
      c[i] += 1
  q = int(readline())
  for _ in range(q):
    l, r = map(int, readline().split())
    print(c[r + 2] - c[l + 1])
main()

Submission status: Wrong Answer

Solution code:

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]

N = 10 ** 5 
primelist = primes(10**5)
prime_add = [0] * (10**5+1)
idx = 0
i = 1
import bisect
L = len(primelist)
while idx < L:
    if i == primelist[idx]:
        tmp = bisect.bisect_right(primelist,(i+1)//2)
        if primelist[tmp-1] == (i+1)//2:
            prime_add[i] = prime_add[i-1] + 1
        else:
            prime_add[i] = prime_add[i-1]
        i += 1
        idx += 1
    else:
        prime_add[i] = prime_add[i-1]
        i += 1
    
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

for l,r in lr:
    print(prime_add[r]-prime_add[l-1])

Submission status: Wrong Answer

Solution code:
import math 

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

#エラトステネスのふるい
MAX =100001
is_prime = [1]*(MAX+1)
is_prime[0],is_prime[1] == 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j <= MAX:
            is_prime[j] = 0
            j += i

#２０１７のような数かどうか
a = [0]*(MAX+1)
for i in range(0,MAX):
    if i % 2 == 1:
        if is_prime[i]==1 and is_prime[int((i+1)/2)]==1:
            a[i] = 1

#累積和
s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]

#クエリ処理
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    r += 1

    print(s[r]-s[l])

Submission status: Wrong Answer

Solution code:
import math 

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

#エラトステネスのふるい
MAX =100000
is_prime = [1]*(MAX+1)
is_prime[0],is_prime[1] == 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j <= MAX:
            is_prime[j] = 0
            j += i

#２０１７のような数かどうか
a = [0]*(MAX+1)
for i in range(0,MAX):
    if i % 2 == 1:
        if is_prime[i]==1 and is_prime[int((i+1)/2)]==1:
            a[i] = 1

#累積和
s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]

#クエリ処理
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    r += 1

    print(s[r]-s[l])

Submission status: Wrong Answer

Solution code:
import math 

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

#エラトステネスのふるい
MAX =100000
is_prime = [1]*(MAX+1)
is_prime[0],is_prime[1] == 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j < MAX+1:
            is_prime[j] = 0
            j += i

#２０１７のような数かどうか
a = [0]*(MAX+1)
for i in range(0,MAX):
    if i % 2 == 1:
        if is_prime[i]==1 and is_prime[int((i+1)/2)]==1:
            a[i] = 1

#累積和
s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]

#クエリ処理
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    r += 1

    print(s[r]-s[l])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
Q = int(input())
ans = []
searchList = [i for i in range(2,10**5+1)]
primeNum = []
primeNumLst = [False]*(10**5+1)

mx = 10**5**0.5+1
while searchList[0] <= mx:
    primeNum.append(searchList[0])
    tmp = searchList[0]
    searchList = [i for i in searchList if i%tmp != 0]
primeNum.extend(searchList)

lst = [0]*(10**5+1)

for p in primeNum:
    primeNumLst[p] = True
    if primeNumLst[(p+1)//2]:
        lst[p] = 1
    
sumlst = list(accumulate(lst))

for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(sumlst[r+1] - sumlst[l-1])
    
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
Q = int(input())
ans = []
searchList = [i for i in range(2,10**5+1)]
primeNum = []
primeNumLst = [False]*(10**5+1)

mx = 10**5**0.5+1
while searchList[0] <= mx:
    primeNum.append(searchList[0])
    tmp = searchList[0]
    searchList = [i for i in searchList if i%tmp != 0]
primeNum.extend(searchList)

lst = [0]*(10**5+1)

for p in primeNum:
    primeNumLst[p] = True
    if primeNumLst[(p+1)//2]:
        lst[p] = 1
    
sumlst = list(accumulate(lst))

for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(sumlst[r] - sumlst[l-1])
    
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
Q = int(input())
ans = []
searchList = [i for i in range(2,10**5+1)]
primeNum = []
primeNumLst = [False]*(10**5+1)

mx = 10**5**0.5+1
while searchList[0] <= mx:
    primeNum.append(searchList[0])
    tmp = searchList[0]
    searchList = [i for i in searchList if i%tmp != 0]
primeNum.extend(searchList)

lst = [0]*(10**5+1)
sumlst = [0]*(10**5+2)

for p in primeNum:
    primeNumLst[p] = True
    if primeNumLst[(p+1)//2]:
        lst[p] = 1
    
for i in range(10**5+1):
    sumlst[i+1] = sumlst[i] + lst[i]

for _ in range(Q):
    l, r = map(int, input().split())
    if l == r:
        if lst[l] == 1:
            ans.append(1)
        else:
            ans.append(0)
    else:
        ans.append(sumlst[r] - sumlst[l])
    
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
Q = int(input())
ans = []
searchList = [i for i in range(2,10**5+1)]
primeNum = []
primeNumLst = [False]*(10**5+1)

mx = 10**5**0.5+1
while searchList[0] <= mx:
    primeNum.append(searchList[0])
    tmp = searchList[0]
    searchList = [i for i in searchList if i%tmp != 0]
primeNum.extend(searchList)

lst = [0]*(10**5+1)
sumlst = [0]

for p in primeNum:
    primeNumLst[p] = True
    if primeNumLst[(p+1)//2]:
        lst[p] = 1
    
for i in lst:
    sumlst.append(sumlst[-1] + i)

for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(sumlst[r+1] - sumlst[l])
    
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
Q = int(input())
ans = []
searchList = [i for i in range(2,10**5+1)]
primeNum = []
primeNumLst = [False]*(10**5+1)

mx = 10**5**0.5+1
while searchList[0] <= mx:
    primeNum.append(searchList[0])
    tmp = searchList[0]
    searchList = [i for i in searchList if i%tmp != 0]
primeNum.extend(searchList)

lst = [0]*(10**5+1)
sumlst = [0]

for p in primeNum:
    primeNumLst[p] = True
    if primeNumLst[(p+1)//2]:
        lst[p] = 1
    
for i in range(10**5+1):
    sumlst.append(sumlst[-1] + i)

for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(sumlst[r+1] - sumlst[l])
    
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
    prime_list[2] = False
    for i in range(3, (n // 2) + 3, 1):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
                j_1 = (j * 2) - 1
                if j_1 <= n:
                    prime_list[j_1] = False
        else:
            i_1 = (i * 2) - 1
            if i_1 <= n:
                prime_list[i_1] = False
    return prime_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])

Submission status: Wrong Answer

Solution code:
def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
        j_1 = (j * 2) - 1
        if j_1 <= n:
            prime_list[j_1] = False
    prime_list[2] = False
    for i in range(3, (n // 2) + 3, 2):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
                j_1 = (j * 2) - 1
                if j_1 <= n:
                    prime_list[j_1] = False
        else:
            i_1 = (i * 2) - 1
            if i_1 <= n:
                prime_list[i_1] = False
    return prime_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])

Submission status: Wrong Answer

Solution code:
def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
        j_1 = (j * 2) - 1
        if j_1 <= n:
            prime_list[j_1] = False
    prime_list[2] = False
    for i in range(3, int(n ** (0.5)) + 1, 2):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
                j_1 = (j * 2) - 1
                if j_1 <= n:
                    prime_list[j_1] = False
        else:
            i_1 = (i * 2) - 1
            if i_1 <= n:
                prime_list[i_1] = False
    return prime_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])

Submission status: Wrong Answer

Solution code:
def Eratosthenes(n):
    prime_list = [True for _ in range(n + 1)]
    prime_list[0] = False
    prime_list[1] = False
    for j in range(4, n + 1, 2):
        prime_list[j] = False
        j_1 = (j * 2) - 1
        if j_1 <= n:
            prime_list[j_1] = False
    prime_list[2] = False
    for i in range(3, int(n ** (0.5)) + 1, 2):
        if prime_list[i]:
            for j in range(i * 2, n + 1, i):
                prime_list[j] = False
                j_1 = (j * 2) - 1
                if j_1 <= n:
                    prime_list[j_1] = False
    return prime_list

q = int(input())
num_list = []
num_max = 0
for _ in range(q):
    l, r = map(int, input().split())
    num_list.append([l, r])
    num_max = max(r, num_max)
prime_list = Eratosthenes(num_max)
prime_num = [0 for _ in range(num_max + 1)]
for i in range(num_max):
    prime_num[i + 1] = prime_num[i] + prime_list[i + 1]

for l, r in num_list:
    print(prime_num[r] - prime_num[l - 1])

Submission status: Wrong Answer

Solution code:
def prime(i):
    if i == 1:
        return False
    if (i > 2) & (i % 2 == 0):
        return False
    for j in range(3, int(i**(0.5)) + 1, 2):
        if i % j == 0:
            return False
    return True



q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    i = l
    while (i <= r):
        if prime(i) & prime(int(i+1)//2):
            ans += 1
            i += 4
        else:
            i += 2
    print(ans)

Submission status: Wrong Answer

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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]]

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
a = [1]*(K+1)
a[0] = 0
a[1] = 0
for i in range(2,K+1):
    if a[i]:
        for j in range(i*i, K+1, i):
            a[j] = 0

for i in range(K):
    a[i+1] += a[i]

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if a[ll]-a[ll-1] == 1:
            print(1)
        else:
            print(0)
    else:
        print(a[rr] - a[ll])

Submission status: Wrong Answer

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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]]

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
ans = [0]
for i in range(K):
    if i % 2 == 0:
        ans.append(ans[-1])
    elif i in prime and (i+1)/2 in prime:
        ans.append(ans[-1]+1)
    else:
        ans.append(ans[-1])
        
for j in range(Q):
    if r[j] == l[j]:
        print(0)
    else:
        print(ans[r[j]]-ans[l[j]])

Submission status: Wrong Answer

Solution code:
def Eratosthenes(n):
    prime = []
    if n <= 1:
        return [] 
    else:
        for i in range(2,n+1):
            prime_judge = True
            for j in range(len(prime)):
                if i % prime[j] == 0:
                    prime_judge = False
                    break
                else:
                    continue
            if prime_judge:
                prime.append(i)
        return prime

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = Eratosthenes(K)
ans = [0]
for i in range(K):
    if i % 2 == 0:
        ans.append(ans[-1])
    elif i in prime and (i+1)/2 in prime:
        ans.append(ans[-1]+1)
    else:
        ans.append(ans[-1])
        
for j in range(Q):
    if r[j] == l[j]:
        print(0)
    else:
        print(ans[r[j]]-ans[l[j]])

Submission status: Wrong Answer

Solution code:
def erastotenes(n):
    prime=[2]
    limit=int(n**0.5)
    data=[i+1 for i in range(2, n, 2)]      #奇数のリストを作成
    while True:
        p=data[0]
        if p>=limit:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

primes=erastotenes(100000)
print("OK")

isLike=[0]*100001
for i in range(1, len(isLike)):
    if i in primes and int((i+1)/2) in primes:
        isLike[i]=isLike[i-1]+1
    else:
        isLike[i]=isLike[i-1]

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(isLike[right]-isLike[left-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect
ref=deque()
refref=deque([2])
for i in range(3,100000,2):
	flag=1
	for j in range(2,int(i**0.5)+1):
		if i%j==0:
			flag=0
			break
	if flag:
		ref.append(i)
for p in ref:
	if (p+1)//2 in ref:
		refref.append(p)
q,*li=map(int,open(0).read().split())
for l,r in zip(li[::2],li[1::2]):
	print(bisect(refref,r+1)-bisect(refref,l-1))

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect
ref=deque()
refref=deque()
for i in range(3,100000,2):
	flag=1
	for j in range(2,int(i**0.5)+1):
		if i%j==0:
			flag=0
			break
	if flag:
		ref.append(i)
for p in ref:
	if (p+1)//2 in ref:
		refref.append(p)
q,*li=map(int,open(0).read().split())
for l,r in zip(li[::2],li[1::2]):
	print(bisect(refref,r+1)-bisect(refref,l-1))

Submission status: Wrong Answer

Solution code:
q = int(input())
like2017 = []

def is_prime(x):
    if x==2:
        return True
    elif x%2==0:
        return False

    for i in range(3, x, 2):
        if x!=i and x%i==0:
            return False
    return True

for i in range(3, 9974, 2):
    if is_prime(i) and is_prime(int((i+1)/2)):
        like2017.append(i)
# print(like2017)
for i in range(q):
    l, r = map(int, input().split())
    left = 0
    right = 0
    for j in like2017:
        if l==1:
            left = 0
        if j < l:
            left = like2017.index(j)
        elif j > r:
            right = like2017.index(j)-1
            break
    print(right-left)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
import math
from itertools import chain

def input():
    return sys.stdin.readline().rstrip()

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())
a = [list(map(int, input().split())) for _ in range(Q)]
s = []
min_num = min(list(chain.from_iterable(a)))
max_num = max(list(chain.from_iterable(a)))
ctr = 0

for j in range(min_num, max_num, 2):
    if is_prime(j) and is_prime((j + 1) // 2):
        s.append(j)

for i in range(Q):
    for k in s:
        if k >= a[i][0] and k <= a[i][1]:
            ctr += 1
    print(ctr)
    ctr = 0

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
import math
from itertools import chain

def input():
    return sys.stdin.readline().rstrip()

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())
a = [list(map(int, input().split())) for _ in range(Q)]
s = []
min_num = min(list(chain.from_iterable(a)))
max_num = max(list(chain.from_iterable(a)))
ctr = 0

for j in range(min_num, max_num, 2):
    if is_prime(j):
        s.append(j)

for i in range(Q):
    for k in s:
        if k >= a[i][0] and k <= a[i][1] and is_prime(k) and is_prime((k + 1) // 2):
            ctr += 1
    print(ctr)
    ctr = 0

Submission status: Wrong Answer

Solution code:
import math
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 10
is_prime = [True] * r_max
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, math.ceil(r_max // i)):
            is_prime[i*j] = False

# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i]-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 10
is_prime = [True] * r_max
is_prime[0] = False
is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i):
            is_prime[i*j] = False

# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1
# print(a)

for i in range(q):
    print(a[r[i]] - a[l[i]-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
l = []
r = []
for i in range(q):
    li, ri = map(int, input().split())
    l.append(li)
    r.append(ri)

r_max = max(r) + 5
is_prime = [True] * (r_max)
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i):
            is_prime[i*j] = False

a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1

for i in range(q):
    print(a[r[i]] - a[l[i]-1])

Submission status: Wrong Answer

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

prime = [1]*(10**5 + 10)
for i in range(2,10**5+10):
    if prime[i]:
        for j in range(2*i,10**5 + 10,i):
            prime[j] = 0

Ans = [0]*(10**5 + 10)

for a in range(1,10**5 + 9):
    if prime[a] and prime[int((a+1)/2)]:
        Ans[a] = 1
    Ans[a] += Ans[a-1]

for l,r in LR:
    print(Ans[r]-Ans[l-1])

Submission status: Wrong Answer

Solution code:
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl=sieve_of_eratosthenes(100000)

p_list = [0 for i in range(100001)]

for p in pl:
    p_list[p]+=1

ps_list = [0]
ps = 0

for i in range(1,100001):
    ps+=p_list[i]
    ps_list.append(ps)

Q = int(input())

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

Submission status: Wrong Answer

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

############
############
############

Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

table = list(range(2, max_r+1))
prime_table = []
for i in range(2, int(max_r**0.5)+1):
    prime_num = table.pop(0)
    prime_table.append(prime_num)
    table = [ i for i in table if i % prime_num != 0]
    if len(table) == 0:
        break

# 1は2017に似てない数字
cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if odd in prime_table and (odd+1)//2 in prime_table:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])

Submission status: Wrong Answer

Solution code:
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

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)

like_numbers = []
for prime in primes:
    if int((prime + 1) / 2) in primes:
        like_numbers.append(prime)

for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    print(sum((x >= l and x <= r) for x in like_numbers))

Submission status: Wrong Answer

Solution code:
import bisect

q = int(input())

def PRIME(N):
    LIM = int(N**0.5)+2
    for i in range(2, LIM):
        if N%i == 0:
            return False
    return True

prime, ans = {2:True}, []
for i in range(3, 100001):
    if i%2 == 0:
        prime[i] = False
        continue
    a = PRIME(i)
    prime[i] = a
    if a:
        if prime[(i+1)//2]:
            ans.append(i)

for _ in range(q):
    l, r = map(int, input().split())
    L = bisect.bisect_left(ans, l)
    R = bisect.bisect_left(ans, r)
    print(R-L)

Submission status: Wrong Answer

Solution code:
Q = int(input())
lr = list(list(map(int,input().split())for i in range(Q)))
pn = [0,0]+[1]*(10**5-2)
O = 0
for i in range(2,317):
    for j in range(i*2,10**5,i):
        pn[j] = 0
p = pn.copy()
for i in range(7,10**5):
    if p[i]==1:
        if(pn[int((i+1)/2)]==0):
            p[i] = 0
tmp = 0
p[2] =0
for i in range(10**5):
    p[i] = tmp+p[i]
    tmp = p[i]
print(p[:30])
for l,r in lr:
    print(p[r]-p[l-1])

Submission status: Wrong Answer

Solution code:
q = int(input())
l = [list(map(int,input().split())) for _ in range(q)]

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
sim_sum = [0]*(10**5+1)

for p in table:
    if p*2-1 in table:
        sim_sum[p] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print(sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)])

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
input = sys.stdin.readline

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

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        if len(cum) > y:
            p = p + cum[y]
        if len(cum) > x:
            p = p - cum[x]
    print(p)