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:
import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    #lnum = base[0:l[i]]
    #rnum = base[0:r[i]]
    print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )

Submission status: Wrong Answer

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

l = [0 for _ in range(Q)]
r = l
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+1)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = 0 #even
  return sn

base = create_list()
#print(base)
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

Submission status: Wrong Answer

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

l = [0 for i in range(Q)]
r = [0 for i in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  if(type(num) != type(0)):
    print('error at '+str(num)+' type = '+str(type(num)))
    print(type(int))
    return 0
  if(num<2):
    return 0
  elif(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for i in range(MAXI)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i,MAXI,i*2):
        prime[j] = 0
      for j in range(i,MAXI,i*3):
        prime[j] = 0
      for j in range(i,MAXI,i*5):
        prime[j] = 0
  sn = [0 for i in range(MAXI+1)]
  for i in range(1,MAXI+1,2):
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = 0 #even
  return sn

base = create_list()
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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]]
prime = primes(10**5)
li = [0]*(10**5)
for i in range(3,10**5,2):
    if i in prime and int((i+1)/2) in prime:
        n = int((i-1)/2)
        li[n] = li[n-1]+1
    else:
        li[n] = li[n-1]
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    ln = int((l-1)/2)
    rn = int((r-1)/2)
    if ln == 0:
        print(li[rn])
    else:
        print(li[rn]-li[ln-1])

Submission status: Wrong Answer

Solution code:
q = int(input())

length = 100010
primes = [1] * length

for i in range(2, len(primes)):
    if primes[i] == 1:
        n = i*2
        while n < length:
            primes[n] = 0
            n += i

a = [0]*length

for i in range(len(a)):
    if i % 2 == 0:
        continue
    # 2017-like
    is2017Like = primes[i] and primes[(i+1) // 2]
    a[i] = (1 if is2017Like else 0)

accum = [0]*(length+1)

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

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

Submission status: Wrong Answer

Solution code:
import math
from itertools import accumulate
def is_prime(n):
  if n==1:
    return False
  for i in range(2,int(math.sqrt(n)+1)):
    if n%i==0:
      return False
  return True
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
  l[i],r[i]=list(map(int,input().split()))
min_l=min(l)
max_r=max(r)
a=[]
for i in range(min_l,max_r+1):
  if i%2==0:
    a.append(0)
  else:
    if is_prime(i) and is_prime((i+1)/2):
      a.append(1)
    else:
      a.append(0)
print(a)
check=[0]+a
check=list(accumulate(check))
for i in range(q):
  print(check[r[i]-min_l+1]-check[l[i]-min_l])

Submission status: Wrong Answer

Solution code:
import math
import sys
from bisect import bisect_left
from math import ceil, sqrt

q = int(sys.stdin.readline().rstrip())
lr = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(q)]


def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    primes = [n for n in range(N+1) if temp[n]]
    return primes


primes = era_prime(100000)
post_primes = []
for pi in primes:
    if (pi + 1) // 2 in primes:
        post_primes.append(pi)


for lri in lr:
    l = bisect_left(post_primes, lri[0])
    r = bisect_left(post_primes, lri[1])
    ans = r - l
    if l >= len(post_primes) or r >= len(post_primes):
        print(0)
        break
    # if post_primes[l] == post_primes[r] and post_primes[l] in lri:
    #     ans += 1
    if post_primes[r] in lri:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys
from bisect import bisect_left
from math import ceil, sqrt

q = int(sys.stdin.readline().rstrip())
lr = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(q)]


def era_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    primes = [n for n in range(N+1) if temp[n]]
    return primes


primes = era_prime(100000)
post_primes = []
for pi in primes:
    if (pi + 1) // 2 in primes:
        post_primes.append(pi)


for lri in lr:
    l = bisect_left(post_primes, lri[0])
    r = bisect_left(post_primes, lri[1])
    if l == len(post_primes):
        l = len(post_primes) - 1
    if r == len(post_primes):
        r = len(post_primes)-1

    ans = r - l
    # if post_primes[l] == post_primes[r] and post_primes[l] in lri:
    #     ans += 1
    if post_primes[r] in lri:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
def sosu_judge(n):
    i = 2
    while i*i <= n:
        if n%i == 0:
            return 0
        i += 1
    return 1

Q = int(input())
C = [list(map(int, input().split())) for i in range(Q)]
for rl in C:
    r, l = rl
    answer = 0
    for j in range(r,l+1):
        if sosu_judge(j) == 1:
            if sosu_judge((j+1)//2) == 1:
                answer += 1
    print(answer)

Submission status: Wrong Answer

Solution code:
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(input())

condition = 10 ** 5

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

kodoku = {2}

for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for div in kodoku:
        if div > lim:
            break
        if i % div == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)

ruisekiwa = [0] * (condition + 5)

for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(input())

condition = 10 ** 5

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

kodoku = {2}

for i in range(3, condition + 2, 2):
    lim = i ** (1 / 2)
    flg = True
    for div in kodoku:
        if div > lim:
            break
        if i % div == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)

ruisekiwa = [0] * (condition + 2)

for i in range(3, condition + 2, 2):
    ruisekiwa[i] = ruisekiwa[i - 2]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 2)]
    print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(input())

condition = 10 ** 5

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

kodoku = {2}

for i in range(3, condition + 1, 2):
    lim = i ** (1 / 2)
    flg = True
    for div in kodoku:
        if div > lim:
            break
        if i % div == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)

ruisekiwa = [0] * (condition + 1)

for i in range(3, condition + 1, 2):
    ruisekiwa[i] = ruisekiwa[i - 2]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 2)]
    print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(input())

condition = 10**5

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

kodoku = {2}

for i in range(3,condition+1,2):
    lim = i**(1/2)
    flg = True
    for div in kodoku:
        if div > lim:
            break
        if i % div ==0:
            flg = False
            break

    if flg:
        kodoku.add(i)

ruisekiwa = [0]*(condition+1)

for i in range(3, condition+1,2):
    ruisekiwa[i] = ruisekiwa[i-2]
    if i in kodoku and (i+1)//2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r]-ruisekiwa[l-2]
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
num = 1000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    s2 = set([i for i in range(l,r+1) if i in p])
    s3 = set([i for i in s2 if (i+1)//2 in p])
    print(len(s3))

Submission status: Wrong Answer

Solution code:
import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    s2 = set([i for i in range(l,r+1)])
    s3 = set([(i+1)/2 for i in s2])
    s3 = s3 & p
    print(len(s3))

Submission status: Wrong Answer

Solution code:
from sys import stdin
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
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
oppai[99992:99999]=[oppai[99991]]*7
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,stdin.readline().strip().split()))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
q=[list(map(int,input().split())) for _ in range(n)]
MAX=100010
p=[1]*MAX
p[0]=0;p[1]=0
for i in range(2,MAX):
  if not p[i]:continue
  for j in range(i*2,MAX,i):p[j]=0
a=[0]*MAX
for i in range(MAX):
  if i%2==0:continue
  if p[i] and p[int((i+1)/2)]:a[i]=1
s=[0]*(MAX+1)
for i in range(MAX):
  s[i+1]=s[i]+a[i]
for i in range(n):
  print(s[q[i][1]]-s[q[i][0]])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ma = lambda : map(int,input().split())
ni = lambda : int(input())

n = 10**5+1
tot = [0]*n
primes = [1]*n
primes[0] =0
primes[1] =0

for i in range(2,n):
    if primes[i] ==1:
        for j in range(2,n//i):
            primes[i*j] = 0
p2017 = [0]*n
for i in range(1,n):
    p2017[i] = p2017[i-1]
    if primes[i] and primes[(i+1)//2]:
        p2017[i]+=1
q = ni()
for i in range(q):
    l,r = ma()
    print(p2017[r]-p2017[l-1])

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

Q = int(input())

dp = {1: 0}

for i in range(10**5)[3::2]:
  if is_prime(i) and is_prime((i+1)//2):
    dp[i] = dp[i-2]+1
  else:
    dp[i] = dp[i-2]

for i in range(Q):
  l, r = list(map(int, input().split()))
  r = dp[r]
  l = dp[l-2] if 3 <= l else 0
  print(r-l)

Submission status: Wrong Answer

Solution code:
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
pn=[2]
qn=[]
for L in range(3, 10**5, 2):
    for L2 in pn:
        if L % L2 == 0:
            break
    else:
        pn.append(L)

    if (L+1)/2 in pn:
        qn.append(L)

for i in range(q):
    print(len([j for j in qn if lr[i][0]<=j<=lr[i][1]]))

Submission status: Wrong Answer

Solution code:
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
pn=[2]
for L in range(3, 10**5, 2):
    for L2 in pn:
        if L % L2 == 0:
            break
    else:
        if (L+1)/2 in pn:
            pn.append(L)
pn.pop(0)
for i in range(q):
    print(len([j for j in pn if lr[i][0]<=j<=lr[i][1]]))

Submission status: Wrong Answer

Solution code:
q=int(input())
pn=[2]
for L in range(3, 10**5, 2):
    for L2 in pn:
        if L % L2 == 0:
            break
    else:
        if (L+1)/2 in pn:
            pn.append(L)
pn.pop(0)
for i in range(q):
    l,r=map(int,input().split())
    print(len([i for i in pn if l<=i<=r]))

Submission status: Wrong Answer

Solution code:
q=int(input())
pn=[2]
for L in range(3, 10**5, 2):
    for L2 in pn:
        if L % L2 == 0:
            break
    else:
        if (L+1)/2 in pn:
            pn.append(L)
pn.pop(0)
print(pn)
c=0
for i in range(q):
    l,r=map(int,input().split())
    c+=len([i for i in pn if l<=i<=r])
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
N = 10**5
c_sum = [0 for i in range(N+2)]
#c_sum[i+1]:iまでの2017-likeな奇数の数
#エラトステネスの篩
primes = [1 for i in range(N+1)]
primes[0], primes[1] = 0, 0
for i in range(N+1):
    if primes[i] == 1:
        for j in range(2*i, int(np.sqrt(N+1))+1, i):
            primes[j] = 0
for i in range(3, N+1):
    if primes[i] == 1 and primes[int((i+1)/2)] == 1:
        c_sum[i+1] = c_sum[i] + 1
    else:
        c_sum[i+1] = c_sum[i]
for i in range(Q):
    l, r = map(int, input().split())
    r += 1
    print(c_sum[r] - c_sum[l])

Submission status: Wrong Answer

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

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

prime_numbers = [is_prime(i) for i in range(2, 10**5 + 1) if is_prime(i) != 0]
# print(prime_numbers)
same = [0]*(10**5 + 1)
for n in prime_numbers:
    # print(n)
    if (n+1) // 2 in prime_numbers:
        same[n] += 1
# print(same)
# print(same[:20])

for i in range(10**5):
    same[i+1] += same[i]
# print(same[:20])
# print(same[3], same[5])
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    N = same[r] - same[l]
    if same[l] != same[l-1] or same[r] != same[r-1]:
        N += 1
        if l == r:
            N += 1
    ans.append(N)

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

Submission status: Wrong Answer

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

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

prime_numbers = [is_prime(i) for i in range(2, 10**5 + 1) if is_prime(i) != 0]
# print(prime_numbers)
same = [0]*(10**5 + 1)
for n in prime_numbers:
    # print(n)
    if (n+1) // 2 in prime_numbers:
        same[n] += 1
# print(same)
for i in range(10**5):
    same[i+1] += same[i]
# print(same)
# print(same[3], same[5])
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    N = same[r] - same[l]
    if same[r] != same[r-1]:
        N += 1
    if same[l] != same[l-1]:
        N += 1
    if r == l:
        N -= 1
    # print(N)
    ans.append(N)

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

Submission status: Wrong Answer

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


def main():
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split(' '))
        if L % 2 == 0:
            L += 1
        cnt = 0
        for i in range(L, R + 1, 2):
            if prime_number(i):
                if prime_number((i + 1) // 2):
                    cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


# 素数判定
def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0
    prime=[]

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = 2 * i
            while j <= n:
                is_prime[j - 1] = 0
                j += i
    for i in range(n):
        if is_prime[i]==1:
            prime.append(i+1)
    return prime


# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(pow(10,2))
ans=[]
for i in range(len(v)):
    x=(v[i]+1)//2
    index = bisect.bisect_left(v, x)
    if v[index]==x:
        ans.append(v[i])

for i,j in s:
    r = bisect.bisect_left(ans, j+1)
    l = bisect.bisect_left(ans, i-1)
    print(r-l)

Submission status: Wrong Answer

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


# 素数判定
def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0
    prime=[]

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = 2 * i
            while j <= n:
                is_prime[j - 1] = 0
                j += i
    for i in range(n):
        if is_prime[i]==1:
            prime.append(i)
    return prime


# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(pow(10,5))
ans=[]
for i in range(len(v)):
    x=(v[i]+1)//2
    index = bisect.bisect_left(v, x)
    if v[index]==x:
        ans.append(v[i])

for i,j in s:
    r = bisect.bisect_left(ans, j+1)
    l = bisect.bisect_left(ans, i-1)
    print(r-l)

Submission status: Wrong Answer

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


# 素数判定
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        P.append(a)

    return P

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(100)
ans=[]
for i in range(len(v)):
    x=(v[i]+1)//2
    index = bisect.bisect_left(v, x)
    if v[index]==x:
        ans.append(v[i])

for i,j in s:
    r = bisect.bisect_left(ans, j+1)
    l = bisect.bisect_left(ans, i-1)
    print(r-l)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc084/tasks/abc084_d
# 18:49-19:10 中断
# 0:21-1:10 done


def prime_set(limit=10**5):
    ret = [2]
    for x in range(3, limit+1, 2):
        is_prime = True
        sqrtx = int(pow(x, 0.5))

        for p in ret:
            if p > sqrtx:
                break

            if x % p == 0:
                is_prime = False
                break

        if is_prime:
            ret.append(x)

    return ret


def bin_search(xs, start, end, x):
    idx = start + (end-start) // 2
    if x < xs[idx]:
        return bin_search(xs, start, idx, x)
    elif x > xs[idx]:
        return bin_search(xs, idx+1, end, x)
    else:
        return idx


def geq_search(xs, start, end, x):
    if end - start < 3:
        if x <= xs[start]:
            return start
        else:
            return start+1

    idx = start + (end-start) // 2

    if x <= xs[start]:
        return start
    elif xs[idx-1] < x <= xs[idx]:
        return idx

    if x < xs[idx]:
        return geq_search(xs, start, idx+1, x)
    elif x > xs[idx]:
        return geq_search(xs, idx, end, x)
    else:
        return idx


def leq_search(xs, start, end, x):
    if end - start < 3:
        if x >= xs[start+1]:
            return start+1
        else:
            return start

    idx = start + (end-start) // 2

    if x >= xs[end-1]:
        return end-1
    elif xs[idx-1] <= x < xs[idx]:
        return idx-1

    if x < xs[idx]:
        return leq_search(xs, start, idx+1, x)
    elif x > xs[idx]:
        return leq_search(xs, idx, end, x)
    else:
        return idx


def main():
    # primes = prime_set(100)
    # print(primes)
    # print(leq_search(primes, 0, len(primes), 11))
    # print(leq_search(primes, 0, len(primes), 12))
    # print(leq_search(primes, 0, len(primes), 16))
    # print(leq_search(primes, 0, len(primes), 17))
    # exit()

    primes = prime_set()
    primes_set = set(primes)
    len_primes = len(primes)

    Q = int(input())
    l, r = [None] * Q, [None] * Q
    for i in range(Q):
        l[i], r[i] = map(int, input().split())

    # output = 0
    likes = []
    for x in primes[1:]:
        if (x+1) // 2 in primes_set:
            likes.append(x)
    n_likes = len(likes)

    for i in range(Q):
        left = geq_search(likes, 0, n_likes, l[i])
        right = leq_search(likes, 0, n_likes, r[i])

        output = right - left + 1 if right >= left else 0
        print(output)

    # for i in range(Q):
    #     output = 0

    #     left, right = l[i], r[i]
    #     while True:
    #         if left in primes_set:
    #             break

    #         left += 2
    #     while True:
    #         if right in primes_set:
    #             break

    #         right -= 2

    #     left_idx = bin_search(primes, 0, len_primes, left)
    #     right_idx = bin_search(primes, 0, len_primes, right)

    #     for x in primes[left_idx:right_idx+1]:
    #         if (x + 1) // 2 in primes_set:
    #             output += 1

    #     print(output)
    # # return output


main()
# print(main())

Submission status: Wrong Answer

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

q = int(input())
list_Q = [ list(map(int,input().split(" "))) for i in range(q)]

num = pow(10,5)
list_PRE = [0]*(2*num+10)
list_PRE[2] = 1
for i in range(1, 2*num+10, 2):
    if len(prime_factorize(i)) == 1:
        list_PRE[i] = 1

list_2017 = [0]*(2*num+10)
for i in range(1, num+1, 2):
    if list_PRE[i] == 1 and list_PRE[(i+1)//2] == 1:
        list_2017[i] = 1

list_ANS = [0]
cnt = 0
for i in list_2017:
    if i == 1:
        cnt += 1
        list_ANS.append(cnt)
    else:
        list_ANS.append(cnt)

for i, j in list_Q:
    print(list_ANS[j]-list_ANS[i])

Submission status: Wrong Answer

Solution code:

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

LIST = eratosthenes(10000)

NEW = []
ANS = [0] * 10001
t = 1
for i in LIST:
    if (i+1)//2 in LIST:
        # NEW.append(i)
        ANS[i] = t
        t +=1
q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    B = ANS[a:b+1]
    print(b - a + 1 - B.count(0))

Submission status: Wrong Answer

Solution code:

import math


def query(ql, qr, buckets, like2017):
    ans = 0
    for st, ed, count in buckets:
        # 完全に含まれていればそのままカウント
        if ql < st and ed < qr:
            ans += count
            continue

        # 左にはみ出している
        if st < ql <= ed and ed <= qr:
            for x in range(ql, ed + 1):
                ans += like2017[x]
            continue

        # 右にはみ出している
        if ql < st and st <= qr < ed:
            for x in range(st, qr + 1):
                ans += like2017[x]
            continue

        # 収まっている
        if st <= ql and qr <= ed:
            for x in range(ql, qr + 1):
                ans += like2017[x]
            break
    return ans
        

def submit():
    n_max = 10**5

    # n_maxまでの素数を数える
    is_prime = {x: True for x in range(1, n_max + 1)}
    is_prime[1] = False
    for x in range(2, math.ceil(math.sqrt(n_max)) + 1):
        if is_prime[x]:
            y = 2 * x
            while y <= n_max:
                is_prime[y] = False
                y += x

    like2017 = {}
    for x in range(1, n_max + 1):
        like2017[x] = x % 2 and is_prime[x] and is_prime[(x + 1) // 2]
    
    # バケット法で数えておく
    bucket_size = math.floor(math.sqrt(n_max))
    buckets = []
    
    for st in range(1, n_max + 1, bucket_size):
        ed = st + bucket_size - 1
        bucket_count = sum([like2017[x] for x in range(st, ed + 1) if x <= n_max])
        buckets.append([st, ed, bucket_count])
    
    # クエリを処理する
    q = int(input())
    queries = []
    for _ in range(q):
        queries.append(list(map(int, input().split())))
        
    for q in queries:
        res = query(q[0], q[1], buckets, like2017)
        print(res)


submit()