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):


import math

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0  else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

n=100000
input_list = sieve_of_erastosthenes(n)
prime_list = [i for i, b in enumerate(input_list) if b == True]





count=[0 for i in range(100002)]
for i in prime_list:
  count[i]=1


nitakazu_count=[0 for i in range(100002)]
for i in range(50001):
  if count[2*i+1]==1 and count[i+1]==1:
    nitakazu_count[2*i+1]=1
  
  
ruiseki_count=[0 for i in range(100002)]
for i in range(100000):
  ruiseki_count[i+1]=ruiseki_count[i]+nitakazu_count[i+1]


nn=int(input())

for i in range(nn):
  aa,bb=[int(i) for i in input().split()]
  print(ruiseki_count[bb]-ruiseki_count[aa-1])

Solution (Python):

def isPrime(num):
    a = 2
    if num == 1:
        return False

    while num >= a*a:
        if num%a == 0:
            return False
        a += 1

    return True

if __name__ == '__main__':
    q = int(input())
    a = []
    b = {}
    c = []
    for tmp in range(q):
        l, r = map(int, input().split())
        a.append((l,r))

    for tmp in range(1, (10**5)+1):
        factor = (tmp+1)/2
        if isPrime(tmp) and factor == int(factor) and isPrime(factor):
            b[tmp] = 1
        else:
            b[tmp] = 0
    
    c.append(b[1])
    for tmp in range(2,(10**5)+1):
        if b[tmp]:
            c.append(c[len(c)-1]+1)
        else:
            c.append(c[len(c)-1])

    for tmp in a:
        threshold = tmp[0]-2
        if threshold < 0:
            print(c[tmp[1]-1])
        else:
            print(c[tmp[1]-1]-c[threshold])

Solution (Python):

n = 100010;

a = [0] * n

isprime = [1] * n
isprime[0] = isprime[1] = 0

for i in range(2, n):
    if isprime[i]:
        for j in range(i * i, n, i):
            isprime[j] = 0
for i in range(3, n, 2):
    if isprime[i] and isprime[(i + 1) // 2]:
        a[i] = 1
for i in range(1, n - 1):
    a[i + 1] += a[i]
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])

Solution (Python):





import sys, math
from itertools import accumulate

MAX_N = 100000

def sieve():
  isprime = [i >= 2 for i in range(MAX_N + 1)]
  for p in range(2, MAX_N + 1):
    if isprime[p]:
      for q in range(p + p, MAX_N + 1, p):
        isprime[q] = False
  return isprime

def isPrime(n):
  isPrime._ = isPrime._ or sieve()
  return isPrime._[n]
isPrime._ = None

def is2017like(n):
  return isPrime(n) and isPrime((n + 1) // 2)


def n2017likeUnder(n):
  if n2017likeUnder._ == None:
    lis = [1 if is2017like(i) else 0 for i in range(MAX_N + 1)]
    n2017likeUnder._ = list(accumulate(lis))
  return n2017likeUnder._[n]
n2017likeUnder._ = None


def solve(l, r):
  return n2017likeUnder(r) - n2017likeUnder(l - 1)

Q = int(sys.stdin.readline())
for i in range(Q):
  l, r = [int(w) for w in sys.stdin.readline().split()]
  print(solve(l, r))

Solution (Python):
import math

def isPrimeNumber(num):
    isPrimeNum = True
    for i in range(2,math.floor(math.sqrt(num)) + 1):
        if num % i == 0:
            isPrimeNum = False

    if num == 1:
        isPrimeNum = False

    return isPrimeNum

def is2017alikeNum(num):
    is2017alikeNum = False
    alikeNum = (num + 1) / 2
    if isPrimeNumber(num) and isPrimeNumber(alikeNum):
        is2017alikeNum = True
    return is2017alikeNum

count = 0
list = []
for i in range(1,100000,2):
    if is2017alikeNum(i):
        count += 1
    list.append(count)

N = int(input())
inputList = []
for count in range(0,N):
    l,r = map(int, input().split())
    tempList = [l,r]
    inputList.append(tempList)

for i in range(0,N):
    l = inputList[i][0]
    r = inputList[i][1]
    lIndex = int((l-1)/2)
    rIndex = int((r-1)/2)
    if lIndex == 0:
        lIndex += 1
    x = list[rIndex] - list[lIndex-1]

    print(x)

Solution (Python):

import math
def is_prime(x):
    if(x%2==0):return 0
    else:
        a = 3
        while(a<=math.sqrt(x)):
            if(x%a==0):return 0
            a += 2
    return 1
 
q = int(input())
MAX = 10**5+2
prime = [0 for i in range(MAX)]
alike = [0 for i in range(MAX)]
num = [0 for i in range(MAX)]
prime[2],prime[3] = 1,1
for i in range(4,MAX):
    prime[i] = is_prime(i)
for i in range(1,MAX-1,2):
    if(prime[i]==1 and prime[(i+1)//2]==1):
        alike[i] = 1
    num[i] = num[i-2]+alike[i]
    num[i+1] = num[i]
for i in range(q):
    l, r = list(map(int,input().split()))
    print(num[r]-num[l-1])

Solution (Python):

import math
def is_prime(x):
    if(x%2==0):return 0
    else:
        a = 3
        while(a<=math.sqrt(x)):
            if(x%a==0):return 0
            a += 2
    return 1
 
q = int(input())
MAX = 10**5+2
prime = [0 for i in range(MAX)]
alike = [0 for i in range(MAX)]
num = [0 for i in range(MAX)]
prime[2],prime[3] = 1,1
for i in range(4,MAX):
    prime[i] = is_prime(i)
for i in range(1,MAX-1,2):
    if(prime[i]==1 and prime[(i+1)//2]==1):
        alike[i] = 1
    num[i] = num[i-2]+alike[i]
    num[i+1] = num[i]
for i in range(q):
    l, r = list(map(int,input().split()))
    print(num[r]-num[l-1])

Solution (Python):

import math
def is_prime(x):
    if(x%2==0):return 0
    else:
        a = 3
        while(a<=math.sqrt(x)):
            if(x%a==0):return 0
            a += 2
    return 1

q = int(input())
MAX = 10**5+2
prime = [0 for i in range(MAX)]
alike = [0 for i in range(MAX)]
num = [0 for i in range(MAX)]
prime[2],prime[3] = 1,1
for i in range(4,MAX):
    prime[i] = is_prime(i)
for i in range(1,MAX-1,2):
    if(prime[i]==1 and prime[(i+1)//2]==1):
        alike[i] = 1
    num[i] = num[i-2]+alike[i]
    num[i+1] = num[i]
for i in range(q):
    l, r = list(map(int,input().split()))
    print(num[r]-num[l-1])

Solution (Python):
f = [False for i in range(100001)]
c = [0 for i in range(100001)]


i = 2
while i<100001:
    if not f[i]:
        
        j = 2*i
        while j < 100001:
            f[j] = True
            j += i
    i += 1

i = 3

while i < 100001:
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
    i += 2

i = 3
while i < 100001:

    c[i] += c[i-1]
    i += 1
n = int(input())
while n:
    l, r = list(map(int, input().split()))
    print (c[r]-c[l-1])
    n -= 1

Solution (Python):
f = [False for i in range(100001)]
c = [0 for i in range(100001)]

for i in range(2, 100001):
    if not f[i]:
        for j in range(2*i, 100001, i):
            f[j] = True
for i in range(3, 100001, 2):
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
for i in range(3, 100001):
    c[i] += c[i-1]
    
n = int(input())
while n:
    l, r = list(map(int, input().split()))
    print (c[r]-c[l-1])
    n -= 1

Solution (Python):
def d_2017LikeNumber(Q, I):  
    def prime_list(M):
        
        s = [True] * (M + 1)  
        s[0] = s[1] = False
        for x in range(2, int(M**0.5) + 1):
            if s[x]:
                for i in range(x + x, len(s), x):
                    
                    s[i] = False
        return s

    def calc_like2017(M, p):
        
        
        
        c = [0] * (M + 1)
        for i in range(3, M + 1, 2):  
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, M + 1):
            c[i] += c[i - 1]
        return c

    c = calc_like2017(10**5, prime_list(10**5))
    ans = ''
    for query in I:
        l, r = query[0], query[1]
        ans += '{}\n'.format(c[r] - c[l - 1])
    return ans[:-1]

Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_2017LikeNumber(Q, I))

Solution (Python):
def d_2017LikeNumber(Q, I):  
    def prime_list(M):
        
        s = [True] * (M + 1)  
        for x in range(2, int(M**0.5) + 1):
            if s[x]:
                for i in range(x + x, len(s), x):
                    
                    s[i] = False
        return s

    def calc_like2017(M, p):
        
        
        
        c = [0] * (M + 1)
        for i in range(3, M + 1, 2):
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, M + 1):
            c[i] += c[i - 1]
        return c

    c = calc_like2017(10**5, prime_list(10**5))
    ans = ''
    for query in I:
        l, r = query[0], query[1]
        ans += '{}\n'.format(c[r] - c[l - 1])
    return ans[:-1]

Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_2017LikeNumber(Q, I))

Solution (Python):

import math
Q = int(input())

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    count_similar = [0 for i in range(n+1)]
    for i in range(1,n+1):
        count_similar[i] = count_similar[i-1]
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            count_similar[i] += 1
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print(cnt[r] - cnt[l-1])

Solution (Python):
from math import ceil, sqrt

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

N = max(map(max, querys))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False
            break

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print(nums[ri] - nums[max(0, li - 2)])

Solution (Python):
N = int(input())

prime = [True] * 100001
like2017 = [0] * 100001
num = 0
for i in range(2, 100001):
  if prime[i]:
    for j in range(i*2, 100001, i):
      prime[j] = False
    if i != 2 and prime[(i+1)//2]:
      num += 1
  like2017[i] = num

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

Solution (Python):
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1


L = []
for i in range(1, int(1e5) + 5):
    flg = i % 2 != 0 and is_prime(i) and is_prime((i + 1) // 2)
    L.append(flg)

cumsum = [0]
for l in L:
    if l:
        cumsum.append(cumsum[-1] + 1)
    else:
        cumsum.append(cumsum[-1])

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

Solution (Python):
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque








def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)


def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



def primes(max_number):
    """
    指定値未満の素数を取得するジェネレータ
    https://qiita.com/Mokkeee/items/93b6b7d59fa256aa1677
    """
    if max_number <= 2:
        raise StopIteration
    yield 2
    is_prime = [1] * max_number
    square_root_of_max = max_number ** 0.5
    for number in range(3, max_number, 2):
        if is_prime[number] is 0:
            continue
        yield number
        if number <= square_root_of_max:
            for multiple in range(number * 2, max_number, number):
                is_prime[multiple] = 0

def main():
	P = list(primes(10**5))
	P = [p for p in P[1:] if (p+1)//2 == P[bisect_left(P, (p+1)//2)]]
	n = I()

	for i in range(n):
		l, r = LI()
		a = bisect_left(P,l)
		b = bisect_right(P,r)
		print(b-a)


if __name__ == '__main__':
	main()

Solution (Python):

def inpl(): return list(map(int, input().split()))
from bisect import bisect , bisect_left

def primes(max_number):
    """
    指定値未満の素数を取得するジェネレータ
    https://qiita.com/Mokkeee/items/93b6b7d59fa256aa1677 よりコピペ
    :param max_number: 最大値
    :return: 素数ジェネレータ
    """
    if max_number <= 2:
        raise StopIteration
    yield 2
    is_prime = [1] * max_number
    square_root_of_max = max_number ** 0.5
    for number in range(3, max_number, 2):
        if is_prime[number] is 0:
            continue
        yield number
        if number <= square_root_of_max:
            for multiple in range(number * 2, max_number, number):
                is_prime[multiple] = 0

P = list(primes(10**5 +1))
P = [p for p in P[1:] if (p+1)//2 == P[bisect_left(P, (p+1)//2)]]

Q = int(input())

for _ in range(Q):
    l, r = inpl()
    print(bisect(P, r) - bisect_left(P, l))

Solution (Python):
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)


dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W



def make_prime_list(n: int):
    num = [True] * n
    num[0] = num[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if num[i]:
            for j in range(i ** 2, n, i):
                num[j] = False

    return num


class CumulativeSum:
    def __init__(self, l):
        self.dp = [0] * (len(l) + 1)
        for i, v in enumerate(l):
            self.dp[i + 1] = v + self.dp[i]

    
    def total(self, left, right):
        assert 0 <= left <= right < len(self.dp)
        return self.dp[right + 1] - self.dp[left]


def main():
    Q = int(input())

    prime_list = make_prime_list(10 ** 5 + 5)
    memo = [0] * (10 ** 5 + 5)
    for i in range(10 ** 5 + 1):
        memo[i] = prime_list[i] and prime_list[(i + 1) // 2]

    c = CumulativeSum(memo)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(c.total(l, r))


if __name__ == '__main__':
    main()

Solution (Python):
"""D - 2017-like Number
"""

import math


class Sieve:
    """Sieve of Eratosthenes.

    List primes up to n.
    """

    def __init__(self, n):
        self.__prime = []
        self.__is_prime = [i >= 2 for i in range(n + 1)]

        for i in range(2, int(math.sqrt(n)) + 1):
            if self.__is_prime[i]:
                for j in range(i * i, n + 1, i):
                    self.__is_prime[j] = False

        for i in range(2, n + 1):
            if self.__is_prime[i]:
                self.__prime.append(i)

    def prime(self):
        return self.__prime

    def is_prime(self, n):
        return self.__is_prime[n]


class Fenwick:
    """Fenwick Tree implementation with 1-based index.

    Valid index: [1, N]
    """

    def __init__(self, N):
        self.fen = [0 for _ in range(N + 1)]

    def add(self, idx, val):
        while idx < len(self.fen):
            self.fen[idx] += val
            idx += idx & (-idx)

    def accum(self, idx):
        ret = 0
        while idx > 0:
            ret += self.fen[idx]
            idx -= idx & (-idx)
        return ret

    def sum(self, begin, end):
        return self.accum(end) - self.accum(begin - 1)


if __name__ == '__main__':
    Q = int(input())  
    A = [0 for _ in range(Q)]  

    SIEVE = Sieve(10 ** 5)

    ACCUM = Fenwick(10 ** 5 + 1)
    for i in range(1, 10 ** 5 + 1):
        if SIEVE.is_prime(i) and SIEVE.is_prime((i + 1) // 2):
            ACCUM.add(i, 1)

    

    for i in range(Q):
        l, r = map(int, input().split())
        A[i] = ACCUM.sum(l, r)

    print('\n'.join(map(str, A)))

Solution (Python):
"""D - 2017-like Number
"""

import math


class Sieve:
    """Sieve of Eratosthenes.

    List primes up to n.
    """

    def __init__(self, n):
        self.__prime = []
        self.__is_prime = [i >= 2 for i in range(n + 1)]

        for i in range(2, int(math.sqrt(n)) + 1):
            if self.__is_prime[i]:
                for j in range(i * i, n + 1, i):
                    self.__is_prime[j] = False

        for i in range(2, n + 1):
            if self.__is_prime[i]:
                self.__prime.append(i)

    def prime(self):
        return self.__prime

    def is_prime(self, n):
        return self.__is_prime[n]


class Fenwick:
    """Fenwick Tree implementation with 1-based index.

    Valid index: [1, N]
    """

    def __init__(self, N):
        self.fen = [0 for _ in range(N + 1)]

    def add(self, idx, val):
        while idx < len(self.fen):
            self.fen[idx] += val
            idx += idx & (-idx)

    def accum(self, idx):
        ret = 0
        while idx > 0:
            ret += self.fen[idx]
            idx -= idx & (-idx)
        return ret

    def sum(self, begin, end):
        return self.accum(end) - self.accum(begin - 1)


if __name__ == '__main__':
    Q = int(input())  
    A = [0 for _ in range(Q)]  

    SIEVE = Sieve(10 ** 5)

    ACCUM = Fenwick(10 ** 5 + 1)
    for i in range(1, 10 ** 5 + 1):
        if SIEVE.is_prime(i) and SIEVE.is_prime((i + 1) // 2):
            ACCUM.add(i, 1)

    

    for i in range(Q):
        l, r = map(int, input().split())
        A[i] = ACCUM.sum(l, r)

    print('\n'.join(map(str, A)))

Solution (Python):
"""D - 2017-like Number
"""

import math


class Sieve:
    """Sieve of Eratosthenes.

    List primes up to n.
    """

    def __init__(self, n):
        self.__prime = []
        is_prime = [i >= 2 for i in range(n + 1)]

        for i in range(2, int(math.sqrt(n)) + 1):
            if is_prime[i]:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False

        for i in range(2, n + 1):
            if is_prime[i]:
                self.__prime.append(i)

    def prime(self):
        return self.__prime


class Fenwick:
    """Fenwick Tree implementation with 1-based index.

    Valid index: [1, N]
    """

    def __init__(self, N):
        self.fen = [0 for _ in range(N + 1)]

    def add(self, idx, val):
        while idx < len(self.fen):
            self.fen[idx] += val
            idx += idx & (-idx)

    def accum(self, idx):
        ret = 0
        while idx > 0:
            ret += self.fen[idx]
            idx -= idx & (-idx)
        return ret

    def sum(self, begin, end):
        return self.accum(end) - self.accum(begin - 1)


if __name__ == '__main__':
    Q = int(input())  
    A = [0 for _ in range(Q)]  

    PRIMES = Sieve(10 ** 5).prime()
    

    IS_PRIME = [False for _ in range(10 ** 5 + 1)]
    for prime in PRIMES:
        IS_PRIME[prime] = True
    

    ACCUM = Fenwick(10 ** 5 + 1)
    for i in range(1, 10 ** 5 + 1):
        if IS_PRIME[i] and IS_PRIME[(i + 1) // 2]:
            ACCUM.add(i, 1)

    

    for i in range(Q):
        l, r = map(int, input().split())
        A[i] = ACCUM.accum(r) - ACCUM.accum(l - 1)

    print('\n'.join(map(str, A)))

Solution (Python):
import math

def is_prime_sqrt(q): 
    if q == 1: 
        return False
    if q == 2: 
        return True
    elif q % 2 == 0: 
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): 
        if q % divisor == 0: 
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): 
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

def sieveyn(n): 
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return s


Q = int(input())
A = [0] * 100001 
A[3] = 1
S = sieveyn(100000)

for i in range(5,100001,4):
    if S[i] and S[int((i+1)/2)]:
        A[i] = 1
for i in range(4,100001):
    A[i] += A[i-1]



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

Solution (Python):
N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

prime=[i for i in range(0, max_n+1)]
prime[1]=0
p_len=len(prime)
for i in range(2,p_len):
	if prime[i]!=0:
		for j in range (i+i,p_len,i):
			prime[j]=0


C=[0 for i in range(max_n+1)]
cnt=0
for i in range(max_n+1):
	if prime[i]!=0 and prime[(i+1)/2]!=0:
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt




for i,j in a:
	print C[j]-C[i-1]

Solution (Python):
N = int(input())

prime = [0,0]+[1]*10**5
for i in range(10**3):
  if prime[i]==0: continue
  for j in range(2*i, 10**5+1, i):
    prime[j]=0
  
cumul = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: cumul+=[1]
    else: cumul+=[0]
  else: cumul+=[0]
    
num_table = [0]
for i in range(10**5):
  num_table+=[num_table[-1]+cumul[i+1]]
  
for i in range(N):
  L,R=map(int,input().split())
  print(num_table[R]-num_table[L-1])

Solution (Python):
N = int(input())
l, r = [], []
for i in range(N):
  L,R=map(int,input().split())
  l+= [L]
  r+= [R]
  
prime = [0,0]+[1]*10**5
for i in range(10**3):
  if prime[i]==0: continue
  for j in range(i+1,10**5+1):
    if j%i==0: prime[j]=0
  
ans = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: ans+=[1]
    else: ans+=[0]
  else: ans+=[0]
ans2= [0]
for i in range(10**5):
  ans2+=[ans2[-1]+ans[i+1]]
for i in range(N): 
  print(ans2[r[i]]-ans2[l[i]-1])

Solution (Python):

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

like = [0] * L
is_like = [False] * L
p = 0
for i in range(1, L):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        is_like[i] = True
        p += 1
    like[i] = p

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

Solution (Python):
Q = int(input())
isPrime = [True] * 100001
for p in range(2, 100001):
    if isPrime[p]:
       for i in range(p * p, 100001, p):
           isPrime[i] = False
isPrime[1],isPrime[2] = False,True

like_2017 = [0] * 100002
for i in range(1,100001):
    if isPrime[i] and isPrime[(i+1)//2]:
        like_2017[i] = like_2017[i-1] + 1
    else:
        like_2017[i] = like_2017[i-1]
        
for i in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r] - like_2017[l-1])