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

Solution code:
#https://qiita.com/masashi127/items/88436e16e3672b387a58
#--------------------------------------------
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]
#print(prime_list)
#print(sum(prime_list))

#--------------------------------------------

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

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]
#print(ruiseki_count)

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
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])

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
#!/opt/local/bin/python3

# AtCoder Beginner Contest 084
# D: 2017-like Number

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)

# the number of 2017-like numbers less than or equal to n.
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

# the number of 2017-like numbers between l and r.
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-       
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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-       
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])

Submission status: Accepted

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

#for i in xrange(2, 100001):
i = 2
while i<100001:
    if not f[i]:
        #for j in range(2*i, 100001, i):
        j = 2*i
        while j < 100001:
            f[j] = True
            j += i
    i += 1

i = 3
#for i in xrange(3, 100001, 2):
while i < 100001:
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
    i += 2

i = 3
while i < 100001:
#for i in xrange(3, 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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端
    def prime_list(M):
        # 0以上M以下の素数のリスト
        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse
        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):
                    # 素数xの倍数は素数ではない
                    s[i] = False
        return s

    def calc_like2017(M, p):
        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト
        # 0番目は0と定義する
        # M以下の素数のリストpを予め作っておく必要がある
        c = [0] * (M + 1)
        for i in range(3, M + 1, 2):  # 0,1,2は定義上2017に似た数にならない
            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))

Submission status: Accepted

Solution code:
def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端
    def prime_list(M):
        # 0以上M以下の素数のリスト
        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse
        for x in range(2, int(M**0.5) + 1):
            if s[x]:
                for i in range(x + x, len(s), x):
                    # 素数xの倍数は素数ではない
                    s[i] = False
        return s

    def calc_like2017(M, p):
        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト
        # 0番目は0と定義する
        # 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))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
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)

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

##### main #####

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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))

Submission status: Accepted

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

# 4近傍（右, 下, 左, 上）
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


# nより小さい素数のリストを生成
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]

    # return sum(l[left] + l[left + 1] + ... + l[right])
    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()

Submission status: Accepted

Solution code:
"""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())  # number of query
    A = [0 for _ in range(Q)]  # answer

    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)

    # print(ACCUM.fen)

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

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

Submission status: Accepted

Solution code:
"""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())  # number of query
    A = [0 for _ in range(Q)]  # answer

    PRIMES = Sieve(10 ** 5).prime()
    # print(PRIMES[:100])

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

    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)

    # print(ACCUM.fen)

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

Submission status: Accepted

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        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): #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): #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[0]からA[100000]までのリスト
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]

#print(A[:100])

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

Submission status: Accepted

Solution code:
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
#print prime

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

#print C


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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])

Submission status: Accepted

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