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
Q = int(input())
prime = [0] + [1] * 10**5
prime[1] = 0
c = [0]
for i in range(1, 10**5 + 1):
    if prime[i]:
        c.append(c[-1] + prime[(i + 1) // 2])
        if i <= 10**2.5:
            for j in range(2, 10**5 // i):
                prime[j * i] = 0
    else:
        c.append(c[-1])
for i in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l-1])

Submission status: Wrong Answer

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

def main():
  n=10**5
  ansl=[]
  sieve=[1-i%2 for i in range(n+1)]
  sieve[0]=0
  for i in range(3,n,2):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]

  for e in lr:
    print(ans[e[1]]-ans[e[0]-1])

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
Q = int(input())

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

n_max = 10**5

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)

while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]

prime = prime +data

ans_ls = [0]*(1+n_max)
for i in prime:
    if (i + 1) // 2 in prime:
        ans_ls[i] = 1
ans_cs = [0]*(1+n_max)
for i in range(n_max):
    ans_cs[i+1] = ans_cs[i]+ans_ls[i+1]
for l,r in ls:
    print(ans_ls[r]-ans_ls[l-1])

Submission status: Wrong Answer

Solution code:
# 69

import itertools

q = int(input())
lr_l = [[int(x) for x in input().split()] for y in range(q)]

n_max = max(itertools.chain.from_iterable(lr_l))

isp_l = [True] * (n_max+1)
isp_l[0] = False
isp_l[1] = False

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

p_l = [int(x) for x in range(n_max+1) if isp_l[x]]

print(p_l)

Submission status: Wrong Answer

Solution code:
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 = [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]


def main():
    Q = int(input())
    LR = [list(map(int, input().split())) for _ in range(Q)]
    N = 10 ** 5

    primes = get_sieve_of_eratosthenes(N)

    t = [0 for _ in range(N + 1)]
    for p in primes:
        a, b = divmod(p + 1, 2)
        if b == 0 and a in primes:
            for i in range(p + 1, N + 1):
                t[i] += 1

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


main()

Submission status: Wrong Answer

Solution code:
import math

def pri_num(n):
    for i in range(2,math.floor(n**0.5)+1):
        if n%i == 0:
            return 0
    return 1

def like_2017(n1):
    f1 = pri_num(n1)
    f2 = pri_num((n1+1)//2)
    return f1*f2

Q = int(input())
for _ in range(Q):
    l,r= map(int,input().split())
    cnt = 0
    for i in range(l,r+1,2):
        cnt += like_2017(i)
    print(cnt)

Submission status: Wrong Answer

Solution code:
is_Prime = [True] * (10**5 + 1)
is_Prime[0] = False
is_Prime[1] = False
for i in range(2, int((10**5+1)**0.5)+1):
    for j in range(2*i, 10**5+1, i):
        is_Prime[j] = False
P = [i for i in range(10**5+1) if is_Prime[i] and is_Prime[(i+1)//2]]
odd = [0 for i in range(10**5+1)]
odd[0] = 0
for i in range(0, len(odd)-1):
    odd[i+1] = odd[i]
    if i in P:
        odd[i+1] += 1
Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    if l != r:
        print(odd[r]-odd[l])
    else:
        if l in P:
            print(1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(3, 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 = primes(10**5)
p_set = set(prime)
like = [3]
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

Q = int(input())
for _ in range(Q):
    l, r = map(int,input().split())
    print(bisect_right(like, r) - bisect_left(like, l))

Submission status: Wrong Answer

Solution code:
Q = int(input())

minl = 10**9
maxr = -1
ans_range = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans_range.append((l, r))

    if l < minl:
        minl = l
    if r > maxr:
        maxr = r

dp = [0] * ((maxr - minl) + 2)

import math
for u in range(minl, maxr+1,1):
    check = (u + 1) / 2

    if not float.is_integer(check) or check == 1:
        dp[u - minl + 1] = dp[u-minl]
        continue

    ok = True
    for y in range(2, int(math.sqrt(check))+1):
        if check % y == 0:
            ok = False
            break

    ok2 = True
    for z in range(2, int(math.sqrt(u))+1):
        if u % z == 0:
            ok2 = False
            break
    
    if ok and ok2:
        # print("found: ", u)
        dp[u - minl + 1] = dp[u-minl] + 1
    else:
        # print("u:", u)
        dp[u - minl + 1] = dp[u-minl]

# print(dp)
for ll, rr in ans_range:
    if ll == rr:
        ans = dp[rr-minl+1] - dp[rr-minl]
    else:
        ans = dp[rr-minl] - dp[ll-minl]
    print(ans)

Submission status: Wrong Answer

Solution code:
Q = int(input())

minl = 10**9
maxr = -1
ans_range = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans_range.append((l, r))

    if l < minl:
        minl = l
    if r > maxr:
        maxr = r

dp = [0] * ((maxr - minl) + 2)

import math
for u in range(minl, maxr+1,1):
    check = (u + 1) / 2

    if not float.is_integer(check):
        dp[u - minl + 1] = dp[u-minl]
        continue

    ok = True
    for y in range(2, int(math.sqrt(check))+1):
        if check % y == 0:
            ok = False
            break

    ok2 = True
    for z in range(2, int(math.sqrt(u))+1):
        if u % z == 0:
            ok2 = False
            break
    
    if ok and ok2:
        # print("found: ", u)
        dp[u - minl + 1] = dp[u-minl] + 1
    else:
        # print("u:", u)
        dp[u - minl + 1] = dp[u-minl]

# print(dp)
for ll, rr in ans_range:
    if ll == rr:
        ans = dp[rr-minl+1] - dp[rr-minl]
    else:
        ans = dp[rr-minl] - dp[ll-minl]
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0

for i in range(n):
    l, r =map(int,input().split())
    print(b[max(0, l - 2)] - b[r])

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[0::2] = 0
for i in range(n):
    e = b[max(0, l[i] - 2)]
    f = b[r[i]]
    print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[0::2] = 0
for i in range(n):
    if l[i] == r[i]:
        if is_prime((l[i]+1)/2):
            print(1)
        else:
            print(0)
    else:
        e = b[max(0, l[i] - 2)]
        f = b[r[i]]
        print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[0::2] = 0
for i in range(n):
    if l[i] == r[i]:
        if is_prime((l[i]+1)/2):
            print(1)
        else:
            print(0)
    else:
        e = b[l[i]-2]
        f = b[r[i]]
        print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
for i in range(n):
    if l[i] == r[i]:
        if is_prime((l[i]+1)/2):
            print(1)
        else:
            print(0)
    else:
        e = b[l[i]-1]
        f = b[r[i]]
        print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] +1
        b[c:d] = add 
        c = d
        add +=1
for i in range(n):
    if l[i] == r[i]:
        if is_prime((l[i]+1)/2):
            print(1)
        else:
            print(0)
    else:
        e = b[l[i]+1]
        f = b[r[i]+1]
        print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] +1
        b[c:d] = add 
        c = d
        add +=1
for i in range(n):
    if l[i] == r[i]:
        if is_prime((l[i]+1)/2):
            print(1)
        else:
            print(0)
    else:
        e = b[l[i]]
        f = b[r[i]]
        print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] +1
        b[c:d] = add 
        c = d
        add +=1
for i in range(n):
    if l[i] == r[i]:
        if is_prime((l[i]+1)/2):
            print(1)
        else:
            print(0)
    else:
        e = b[l[i]-1]
        f = b[r[i]-1]
        print(f - e)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] +1
        b[c:d] = add 
        c = d
        add +=1
for i in range(n):
    if l[i] == r[i] and is_prime((l[i]+1)/2):
        print(1)
    else:
        e = b[l[i]-1]
        f = b[r[i]-1]
        print(f - e)

Submission status: Wrong Answer

Solution code:
Q = int(input())  

for _ in range(Q):
  ans = 0
  l,r = map(int,input().split())
  for i in range(l,r+1):
    if i%2 == 0:
      continue
    cnt_1 = 0
    cnt_2 = 0
    for j in range(2,int(i**0.5+1)):
      if i%j == 0:
        cnt_1 += 1
    if cnt_1 == 0:
      for k in range(2,int((i+1)**0.5+1)):
        if (i+1)%k == 0:
          cnt_2 += 1
      if cnt_2 == 0:
        ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    MAX_NUM = 10 ** 5
    Q = int(input())
    lr = [None] * Q
    for i in range(Q):
        lr[i] = tuple(map(int, input().split()))

    is_prime = [True] * (MAX_NUM + 1)
    is_prime[0] = False
    for i in range(4, MAX_NUM + 1, 2):
        is_prime[i] = False

    is_prime[1] = False
    for i in range(3, MAX_NUM + 1, 2):
        for j in range(2 * i, MAX_NUM // i + 1, i):
            is_prime[j] = False

    num = {}
    num[-1] = 0
    for i in range(1, MAX_NUM + 1, 2):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            num[i] = num[i - 2] + 1
        else:
            num[i] = num[i - 2]

    for l, r in lr:
        print(num[r] - num[l - 2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True

for i in range((mini + 1) // 2, maxi + 1, 2):    
    prime[i] = 1 if judge_prime(i) else 0

for i in range(mini, maxi + 1, 2):
    ans[i] = 1 if prime[i] == prime[(i + 1) // 2] == 1 else 0
#print(ans[1: 15])
for i in range(q):
    #print(ans[l[i]: r[i] + 1])
    print(sum(ans[l[i] - mini: r[i] + 1]))

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

for i in range(2, ceil(sqrt(10**5)+1)):
    if a[i] == 0:
        continue
    else:
        if i == 2:
            a[i] = 0
        for j in range(i*2, len(a), i):
            a[j] = 0
            if j*2 - 1 < len(a):
                a[j*2-1] = 0

q = INT()
p = [LIST() for i in range(q)]
s = list(accumulate(a))

for i in range(q):
    print(s[p[i][1]]-s[p[i][0]-1])

Submission status: Wrong Answer

Solution code:
B = [False]*100005
C = [0]*100005
for i in range(2,100001):
    if not B[i]:
      	for j in range(i+i,100001,i):
          	B[j]=True
for i in range(3,100001,2):
    if not B[i] and not B[(i+1)//2]:
        C[i]+=1
for i in range(3,100001):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a])

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:
import math

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

Q = int(input())
ans = []
for _ in range(Q):
  counter = 0
  l, r = map(int, input().split())
  for odd in range(l, r+1, 2):
    if is_prime(odd) and is_prime((odd+1)/2):
      counter += 1
  ans.append(counter)

for item in ans:
  print(item)

Submission status: Wrong Answer

Solution code:
import math

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

Q = int(input())
ans = []
for _ in range(Q):
  counter = 0
  l, r = map(int, input().split())
  for odd in range(l, r+1, 2):
    if is_prime(odd) and is_prime((odd+1)/2):
      counter += 1
  ans.append(counter)

for item in ans:
  print(item)

Submission status: Wrong Answer

Solution code:
q=int(input())
#lr=[list(map(int,input().split())) for i in  range(q)]
MAX=10**5+1
l=[0]*MAX

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
cnt=0
for i in range(1, MAX, 2):
  if is_prime(i) and is_prime((i+1)/2):
    l[i]=1
    
l2=[0]*(MAX+1)
for i in range(0, MAX):
  l2[i+1]=l2[i]+l[i]
print(l2)

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

Submission status: Wrong Answer

Solution code:
q=int(input())
lr=[list(map(int,input().split())) for i in  range(q)]
MAX=10**5+1
l=[0]*MAX

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
cnt=1  
for i in range(1, MAX, 2):
  if is_prime(i) and is_prime((i+1)/2):
    l[i]=cnt
    cnt+=1
  else:
    l[i]=cnt


for i in range(q):
  #print(l[:lr[i][1]+1],l[:lr[i][0]])
  #print(sum(l[:lr[i][1]+1]) - sum(l[:lr[i][0]]))
  if lr[i][1] == lr[i][0]:
    print(1)
  else:
    print(l[lr[i][1]]-l[lr[i][0]])

Submission status: Wrong Answer

Solution code:
Q=int(input())
array=[]
l=[]
r=[]
for i in range(Q):
  b, c=map(int,input().split())
  kazu=0
  for j in range(b,c+1):
    a=0#判定
    for k in range(2,j):
      if j%k==0:
        a=a+1
        break

    if j%2==1 and a==0:
      for m in range(2,(j+1)//2):
          
          if (j+1)//2%m==0:
          
            a=a+1    
            break

    if a==0:
      kazu=kazu+1
  array.append(kazu)
for i in range(len(array)):
  print(str(array[i]))

Submission status: Wrong Answer

Solution code:
Q=int(input())
array=[]
l=[]
r=[]
for i in range(Q):
  b, c=map(int,input().split())
  kazu=0
  for j in range(b,c+1):
    a=0#判定
    for k in range(2,j):
      if j%k==0:
        a=a+1

    if j%2==1:
      for m in range(2,(j+1)//2):
          
          if (j+1)//2%m==0:
          
            a=a+1    



          
               

    if a==0:
      kazu=kazu+1
  array.append(kazu)
for i in range(len(array)):
  print(str(array[i]))

Submission status: Wrong Answer

Solution code:
MAX_INT = 10**5+1
primes = [True] * (10**5+1)
primes[0], primes[1] = False, False
for i in range(2, int(MAX_INT**0.5)+1):
  if primes[i]:
    for j in range(i*i, int(MAX_INT**0.5)+1, i):
      primes[j] = False

cumsum = [0] * (10**5+1)
for i in range(1, 10**5+1, 2):
  if primes[i] and primes[(i+1)//2]:
      cumsum[i] = 1

for i in range(1, 10**5+1):
  cumsum[i] += cumsum[i-1]

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

Submission status: Wrong Answer

Solution code:
q = int(input())
n = 100001
limit = int(n**0.5)
a = [i for i in range(3, n, 2)]
e = []
for i in range(n):
  p = a[i]
  if limit <= p:
    break
  e = [j for j in a if j%p!=0 ]
print(e)

for i in range(q):
  l,r = map(int, input().split())

Submission status: Wrong Answer

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

n = 10 ** 5
memo = [1] * (n+1)

for i in range(2, n):
  for j in range(2, n):
    if i * j > n:
      break
    memo[i*j] = 0
    
for i in range(n+1):
  x = memo[i]
  if x % 2 == 0 or memo[(x+1) // 2] == 0:
    memo[i] = 0
    
c = [0]

for x in memo[1:]:
  c.append(c[-1]+x)
  
q = int(input())
for i in range(q):
  l, r = map(int, input().split())
  print(c[r] - c[l-1])

Submission status: Wrong Answer

Solution code:
def primes(n):#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
li_p, is_prime = primes(10**5+1)
for i in li_p:
    if  is_prime[(i+1)//2]:
        is_prime[i] = False
res = [0] * (10**5+1)
for i in range(10**5+1):
    if i == 0:
        continue
    if is_prime[i]:
        res[i] = res[i-1] + 1
    else:
        res[i] = res[i-1]
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    if l>0:
        print(res[r] - res[l-1])
    else:
        print(res[r])

Submission status: Wrong Answer

Solution code:
def primes(n):#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
li_p, is_prime = primes(10**5+1)
print(li_p)
for i in li_p:
    if  is_prime[(i+1)//2]:
        is_prime[i] = False
res = [0] * (10**5+1)
for i in range(10**5+1):
    if i == 0:
        continue
    if is_prime[i]:
        res[i] = res[i-1] + 1
    else:
        res[i] = res[i-1]
#print(res)
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    if l>0:
        print(res[r] - res[l-1])
    else:
        print(res[r])

Submission status: Wrong Answer

Solution code:
def create_prime_list(limit):
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes
    
Q = int(input())

p = set(create_prime_list(10**5))

#今注目してる数より左に出てきた「2017に似た数」
n_of_p = [0]*(10**5+2)

for i in range(1,10**5+1):
    if i%2 == 1:
        if i in p and (i+1)//2 in p:
            n_of_p[i+1] = n_of_p[i] + 1
        else:
            n_of_p[i+1] = n_of_p[i]
    else:
        n_of_p[i+1] = n_of_p[i]
        
#print(n_of_p[0:20])

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

Submission status: Wrong Answer

Solution code:
from math import floor,sqrt

def eratosthenes(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, floor(sqrt(n))+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table
  
s = set(eratosthenes(10**5))
l = [0]*(10**5 + 1)
count = 0

for i in range(10**5 + 1):
  if i in s:
    count += 1
    l[i] = count
  else:
    l[i] = count
    
count = 0   
L = [0]*(10**5 + 1)

for i in range(1,50002):
  if l[i] - l[i-1] == 1 and  l[2*i - 1] - l[2*i - 2] == 1:
    count += 1
    L[i] = count
  else:
    L[i] = count
    
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  if L[l] - L[l-1] == 1:
    print(L[r] - L[l] + 1)
  else:
    print(L[r] - L[l])

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 1: 
        return False
    x = 2
    while x*x<=n:
        if n%x==0:
            return False
        x+=1
    return True

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return table

sosuu = sieve(100000)
like_2017 = [i for i in sosuu if is_prime((i+1)//2)]
n = len(like_2017)
like_2017_count = []
index = 0
count = 0
for i in range(100000):
  if i<n and i == like_2017[index]:
    count += 1
    index += 1
  like_2017_count.append(count)
  
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  print(like_2017_count[r-1]-like_2017_count[l-1])

Submission status: Wrong Answer

Solution code:
import math

Q = int(input())

def prime(n):
	if n > 1:
		for i in range(2,math.floor(math.sqrt(n))+1):
			if (n % i) == 0:
				return(False)
				break
		else:
			return(True)
	else:
		return(False)

Numero = [0]*100001
for i in range (1, 50001):
	if prime(2*i+1) == 1 and prime(i+1) == 1:
		for j in range (2*i+1, 100001):
			Numero[j]+=1
	else:
		continue

for i in range (0, Q):
	A, B = map(int, input().split())
	print(Numero[B+1]-Numero[A])

Submission status: Wrong Answer

Solution code:
Q=int(input())
for q in range(Q):
    l,r=map(int,input().split())
    count=0
    for N in range(l,r+1,2):
        if all([N%i for i in range(2,int(N**.5)+1)]) and all([((N+1)/2)%i for i in range(2,int(((N+1)/2)**.5)+1)]):
            count+=1
    print(count)

Submission status: Wrong Answer

Solution code:
q=int(input())
def f(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
for i in range(q):
    
    l,r=map(int,input().split())
    ans=0
    for j in range(l,r+1,2):
        k=(j+1)//2
        l=f(j)
        s=f(k)
        if l[0][0]==j and s[0][0]==k:
            ans+=1
    print(ans)

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):
   l2[i]=l2[i-1]+l[i]
for i in range(X):
   x,y=list(map(int,input().split()))
   print(l2[y]-l2[x-1])