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

Solution (Python):
from itertools import takewhile

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

  @classmethod
  def all_identity(cls, operator, equality, identity, size):
    return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

  @classmethod
  def from_initial_data(cls, operator, equality, identity, data):
    size = 1 << (len(data)-1).bit_length()
    temp = [identity]*(2*size)
    temp[size:size+len(data)] = data
    data = temp

    for i in reversed(range(size)):
      data[i] = operator(data[2*i],data[2*i+1])
    return cls(operator, equality, identity, data)

  
  def __init__(self, operator, equality, identity, data):
    if equality is None:
      equality = lambda a,b: False
    self.op = operator
    self.eq = equality
    self.id = identity
    self.data = data
    self.size = len(data)//2

  def _interval(self, a, b):
    a += self.size
    b += self.size
    ra = self.id
    rb = self.id

    data = self.data
    op = self.op
    while a < b:
      if a & 1:
        ra = op(ra,data[a])
        a += 1
      if b & 1:
        b -= 1
        rb = op(data[b],rb)
      a >>= 1
      b >>= 1
    return op(ra,rb)

  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.size]

  def __setitem__(self, i, v):
    i += self.size
    data = self.data
    op = self.op
    eq = self.eq
    while i and not eq(data[i],v):
      data[i] = v
      v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
      i >>= 1

  def __iter__(self):
    return self.data[self.size:]


def generate_primes():
  from collections import defaultdict
  from itertools import count
  D = defaultdict(list)

  q = 2
  for q in count(2):
    if q in D:
      for p in D[q]:
        D[p+q].append(p)
      del D[q]
    else:
      yield q
      D[q*q].append(q)

from operator import add,eq

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

m = max(r for l,r in Q)


primes = set(takewhile(lambda x: x <= m, generate_primes()))
primes.remove(2)

A = [0]*(m+1)

for p in primes:
  if (p+1)//2 in primes:
    A[p] = 1

A[3] = 1

T = SegmentTree.from_initial_data(add, eq, 0, A)

for l,r in Q:
  print(T[l:r+1])

Solution (Python):



import itertools


INT_END = 10 ** 5 + 1


def sieve_of_eratosthenes(end, typecode="L"):
    """Enumerates the prime numbers below the given integer.

    :param int end: Prime numbers below this integer will be enumerated.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of the prime numbers.
    :rtype: :class:`array.array`
    """

    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2, end):
        if is_prime[i]:
            
            for j in range(2 * i, end, i):
                is_prime[j] = False
    
    return is_prime


class CumulativeSum(object):
    """Constructs the cumulative sum of the elements in the given sequence.

    :param sequence: The sequence to be processed.
    :type sequence: sequence
    """

    def __init__(self, sequence):
        self.cumulative_sum = [0]
        self.cumulative_sum.extend(itertools.accumulate(sequence))

    def partial_sum(self, first, last):
        """Computes the partial sum of the sequence.

        :param first: The index representing the first element of the
                      subsequence.
        :type first: int
        :param last: The index representing the last element of the
                     subsequence.
        :return: The partial sum.
        """
        return self.cumulative_sum[last + 1] - self.cumulative_sum[first]


def enumerate_like_number(end=INT_END):
    is_prime = sieve_of_eratosthenes(end)
    is_like = [False for _ in range(end)]
    for i in range(1, end, 2):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            is_like[i] = True
    return is_like


def main():
    q = int(input())
    cs = CumulativeSum(enumerate_like_number())
    for _ in range(q):
        l, r = (int(z) for z in input().split())
        print(cs.partial_sum(l, r))


if __name__ == '__main__':
    main()

Solution (Python):
N = (10**5)+5

is_prime = [True for _ in range(N)]
is_prime[1] = False
for i in range(2,N) :
    if not is_prime[i] :
        continue
    j = i*2
    while j<N :
        is_prime[j] = False
        j += i

cnt_acc = [0 for _ in range(N)]
for i in range(1,N) :
    cnt_acc[i] = cnt_acc[i-1]
    if is_prime[i] and is_prime[(i+1)//2] :
        cnt_acc[i] += 1

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

Solution (Python):
import math

N = 100001   
prime = [True]*(N+1)
prime[0] = False
prime[1] = False

R = int(math.sqrt(N))

for i in range(2, R+1):
    if prime[i]:
        cnt = 2
        while i * cnt <= N:
            prime[i * cnt] = False
            cnt += 1


def check(n):
    return prime[n] and prime[(n+1)//2]

imos = [0]*(N+2)
for i in range(1, N+1):
    if i % 2 == 1:
        if check(i):
            imos[i] += 1
for i in range(1, N+2):
    imos[i] = imos[i] + imos[i-1]

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

Solution (Python):

import numpy as np
ind_prime = np.ones(10**5+1, dtype="int")


max_prime = int(np.ceil(np.sqrt(10**5)))

if max_prime**2 == 10**5:
    max_prime += 1

ind_prime[0] = 0
ind_prime[1] = 0

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


ind_like_2017 = np.zeros(10**5+1, dtype="int")
for i in range(1, 10**5+1, 2):
    if ind_prime[i] == 1 and ind_prime[(i+1)//2] == 1:
        ind_like_2017[i] = 1
        
ind_like_2017_cum = ind_like_2017.cumsum()

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

Solution (Python):
sz = int(1e5)
isprime = [True for _ in range(sz + 1)]

for i in range(sz + 1):
    if i <= 1:
        isprime[i] = False
    elif isprime[i]:
        j = 2 * i
        while j <= sz:
            isprime[j] = False
            j += i

cnt = [0 for _ in range(sz + 1)]
for i in range(3, sz + 1):
    if i % 2 == 1 and isprime[i] and isprime[(i + 1) // 2]:
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

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

Solution (Python):
MAXN = 10**5+10
sieve = [0,0] + [1]*MAXN
m = 2
while m*m <= MAXN:
    if sieve[m]:
        for n in range(2*m,MAXN,m):
            sieve[n] = 0
    m += 1

ok = [0]*MAXN
cums = [0]
for n in range(MAXN):
    if sieve[n] and sieve[(n+1)//2]:
        ok[n] = 1
    cums.append(cums[-1] + ok[n])

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

Solution (Python):
from itertools import accumulate

def eratosthenes(n):
    prime_table = [False,False,True]+[False if i%2!=0 else True for i in range(n-2)]
    i=3
    while i*i<=n:
        if prime_table[i]:
            j=i*i
            while j<=n:
                prime_table[j]=False
                j+=i
        i+=2
    return prime_table

pt=eratosthenes(100000)
ok=[0 for i in range(100000)]
i=1
while i<100000:
    if pt[i] and pt[(i+1)//2]:
        ok[i]=1
    i+=2
ok=list(accumulate(ok))

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

Solution (Python):
M = 10**6
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 4*10**4):
    if p[i]:
        for j in range(i*i, M, i):
            p[j] = 0
C = [0]*M
for i in range(2, M):
    if p[i] and p[(i+1)//2]:
        C[i] = C[i-1] + 1
    else:
        C[i] = C[i-1]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(C[r] - C[l-1])

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

a = [0] * 100005

isp = [1] * 100005
isp[0] = isp[1] = 0
for i in range(2, 100005):
    if isp[i]:
        for j in range(i*i, 100005, i):
            isp[j] = 0
for i in range(3, 100005, 2):
    if isp[i] and isp[(i+1)//2]:
        a[i] = 1
for i in range(1, 100004):
    a[i+1] += a[i]

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