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

'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False

        return self._values


def main():
    from itertools import accumulate

    q = int(input())
    max_n = 10 ** 5 + 100
    prime = Prime(max_n)
    primes = prime.generate()
    like_numbers = [0 for _ in range(max_n + 1)]

    for current_prime in primes:
        new_prime = Prime((current_prime + 1) // 2)

        if new_prime.is_included():
            like_numbers[current_prime] = 1

    like_number_count = list(accumulate(like_numbers))

    for i in range(q):
        li, ri = map(int, input().split())
        print(like_number_count[ri] - like_number_count[li - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

max_n = 10**5
sq = int(math.sqrt(max_n))

prime = [i for i in range(max_n+1)]
prime[1] = 0
for i in prime:
    if i > sq:
        break
    if i == 0:
        continue
    for j in range(i*2, max_n+1, i):
        prime[j] = 0

memo = [0 for i in range(max_n+1)]
for i in range(3, max_n+1, 2):
    if prime[i] != 0 and prime[(i+1)//2] != 0:
        memo[i] = 1

for i in range(max_n):
    memo[i+1] += memo[i]

for l, r in query:
    print(memo[r] - memo[l-1])

Submission status: Accepted

Solution code:
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]

x=10**5+1
import math 
L=math.floor(math.sqrt(x))#平方根を求める

Primelist=[i for i in range(x+1)]
Primelist[1]=0#1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

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

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

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

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from bisect import bisect_left, bisect_right

# 半開区間[lower, upper)の素数のリストを作成する
def make_prime_list(lower:int, upper:int) -> list:
    
    # 素数リストの初期化    
    isPrime = [True]*upper
    primeList = []
    
    # 区間内の数字が0,1のみならここで終了
    if upper <= 2:
        return primeList
    
    # 区間内の数字に2以上のものがあるとき
    isPrime[0] = False
    isPrime[1] = False
    
    # エラトステネスの篩の処理
    for n in range(2,int(sqrt(upper))+2):
        if isPrime[n]:
            res=2*n
            while res<upper:
                isPrime[res] = False
                res += n
    
    # 区間内の素数を抽出
    for n in range(lower,upper):
        if isPrime[n]:
            primeList.append(n)
        
    return primeList

q = ni()
query = [tuple(li()) for _ in range(q)]

prime_list = set(make_prime_list(2,10**5+1))

like2017 = []

for i in range(3, 10**5, 2):
    if (i in prime_list) and ((i+1)//2 in prime_list):
        like2017.append(i)
        
for l,r in query:
    print(bisect_right(like2017, r) - bisect_left(like2017, l))

Submission status: Accepted

Solution code:
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

MAXN = 10**5+10
sieve = [0,0] + [1]*MAXN
p = 2
while p*p <= MAXN:
    if sieve[p]:
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

cums = [0]
for i in range(1,MAXN):
    valid = sieve[i] and sieve[(i+1)//2]
    cums.append(cums[-1] + int(valid))

for l,r in qs:
    ans = cums[r] - cums[l-1]
    print(ans)

Submission status: Accepted

Solution code:
import math
p=[0 for k in range(100000)]
p[1]=1
for k in range(3,100000,2):
    f=1
    for l in range(2,int(math.sqrt(k))+1):
        if k%l==0:
            f=0
            break
    if f==1:
        p[k]=1
c=[0 for k in range(100000)]
c[3]=1
for k in range(3,100000,2):
    if p[k] and p[(k+1)//2]:
        c[k]=1
for k in range(1,100000):
    c[k]+=c[k-1]
for k in range(int(input())):
    l,r=map(int,input().split())
    print(c[r]-c[l-1])

Submission status: Accepted

Solution code:
def primes(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]]


prime_list = primes(100000)
ruiseki = [0] * 100010
tmp = 0

for i in prime_list:
    if int((i+1)/2) in prime_list:
        for j in range(1,i - tmp + 1):
            ruiseki[tmp+j] = ruiseki[tmp]
        ruiseki[i] += 1
        tmp = i
    if i == prime_list[-1]:
        for i in range(tmp,100000):
            ruiseki[i+1] = ruiseki[i]

Q = int(input())
l,r = [],[]
for i in range(Q):
    a,b = map(int,input().split())
    l.append(a)
    r.append(b)

for i in range(Q):
    print(ruiseki[r[i]] - ruiseki[l[i]-1])

Submission status: Accepted

Solution code:
def primes(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]]


prime_list = primes(100000)
ruiseki = [0] * 100010
tmp = 0

rrr = []
for i in prime_list:
    if int((i+1)/2) in prime_list:
        for j in range(1,i - tmp + 1):
            ruiseki[tmp+j] = ruiseki[tmp]
        ruiseki[i] += 1
        tmp = i
        rrr.append(tmp)
    if i == prime_list[-1]:
        for i in range(tmp,100000):
            ruiseki[i+1] = ruiseki[i]

#for i in rrr:
#    ruiseki[i] -= 1

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

Submission status: Accepted

Solution code:
list1=[1 for i in range(100001)]
list1[0]=0
list1[1]=0
for j in range(2,100001):
    if list1[j]==0:
        pass
    else:
        for k in range(2,100001):
            if j*k>100000:
                break
            else:
                list1[j*k]=0
#print(list1[:100])
list2=[0]
for l in range(1,100001):
    if list1[l]==0:
        list2.append(list2[l-1])
    else:
        if list1[int((l+1)/2)]==1:
            list2.append(list2[l-1]+1)
        else:
            list2.append(list2[l-1])
#print(list2[:100])
Q=int(input())
for x in range(Q):
    l,r=map(int,input().split())
    print(list2[r]-list2[l-1])

Submission status: Accepted

Solution code:
listS=[1]*100005
listS[0]=0
listS[1]=0
for i in range(2,100003):
    if listS[i]==1:
        for j in range(2*i,100000,i):
            listS[j]=0
list2017=[0]
for k in range(1,100001):
    if listS[k]==1 and listS[int((k+1)/2)]==1:
        list2017.append(list2017[k-1]+1)
    else:
        list2017.append(list2017[k-1])

N=int(input())
for x in range(N):
    l,m=map(int,input().split())
    print(list2017[m]-list2017[l-1])

Submission status: Accepted

Solution code:
Q=int(input())

prime=[1]*100000
sum2017=[0]*100000
count=0
for i in range(2,10**5):
  if prime[i-1]==1:
    for j in range(i-1+i,10**5,i):
      prime[j]=0
for i in range(0,10**5,2):
  if prime[i]==1 and prime[i//2]==1:
    count+=1
  sum2017[i]=count
  
for i in range(Q):
  l,r=map(int,input().split())
  if l!=1 and sum2017[l-1]!=sum2017[l-3]:
    print(sum2017[r-1]-sum2017[l-1]+1)
  else:
    print(sum2017[r-1]-sum2017[l-1])

Submission status: Accepted

Solution code:
p = []
for n in range(2, 100000):
    isP = True
    for m in p:
        if m ** 2 > n:
            break
        if n % m == 0:
            isP = False
            break
    if isP:
        p.append(n)

p = set(p)

s = {-1: 0}
for n in range(1, 100000, 2):
    s[n] = s[n - 2]
    if n in p and (n + 1) / 2 in p:
        s[n] += 1

Q = int(input())

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

Submission status: Accepted

Solution code:
NMAX = 10**5+1

is_prime = [True]*NMAX
for i in range(2, NMAX):
    if is_prime[i]:
        for j in range(2*i, NMAX, i):
            is_prime[j] = False

sim_2017 = [0]*NMAX
for i in range(3, NMAX, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        sim_2017[i] += 1
for i in range(1, NMAX):
    sim_2017[i] += sim_2017[i-1]

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

Submission status: Accepted

Solution code:
import math
RMAX = 10**5

def get_primes(n):
    ps = []
    upper = math.sqrt(n)
    data = [i+1 for i in range(1, n)]
    while True:
        p = data[0]
        if p >= upper:
            break
        ps.append(p)
        data = [e for e in data if e%p != 0]
    return ps + data

primes = get_primes(RMAX)
primes_set = set(primes)
sim_2017 = [0]*(RMAX+1)
for p in primes:
    if (p+1)//2 in primes_set:
        sim_2017[p] = 1

for i in range(1, len(sim_2017)):
    sim_2017[i] += sim_2017[i-1]

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

Submission status: Accepted

Solution code:
# !/usr/bin/env python
# -*- coding: utf-8 -*-
import math


def generate_prime(p_max):
    prime = [2]
    for i in range(3, p_max + 1):
        for p in prime:
            if i % p == 0:
                break
            if p > math.sqrt(i):
                prime.append(i)
                break
    return prime


def main():
    prime = generate_prime(10**5)
    prime = set(prime)
    prime2 = set()
    for p in prime:
        if p == 2:
            continue
        if (p + 1) / 2 in prime:
            prime2.add(p)
    ans = [0] * (10**5 + 1)
    for i in range(1, 10**5 + 1):
        if i in prime2:
            ans[i] = ans[i - 1] + 1
        else:
            ans[i] = ans[i - 1]

    q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(q)]
    for query in queries:
        print(ans[query[1]] - ans[query[0] - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
Q = int(input())

p = np.array([i for i in range(2*10**5+1)])
p[1]=0
for i in range(2,10**5):
    p[2*i::i] = 0
p = p[p!=0]

dic = {i:1 for i in p}
d = {}
for i in range(len(p)):
    if dic.get((p[i]+1)//2,0)==1:
        d[p[i]] = 1
sum_=0
arr = [0 for i in range(10**5+2)]
for i in range(10**5+2):
    arr[i] = sum_
    if d.get(i,0)==1:
        sum_+=1
for _ in range(Q):
    l,r = list(map(int,input().split()))
    print(arr[r+1]-arr[l])

Submission status: Accepted

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

# エラトステネスの篩
prime = [False] * Q
like2017 = [0] * Q
for i in range(2, Q):
    if not prime[i]:
        for j in range(i*2, Q, i):
            prime[j] = True

# 2017っぽい数
for i in range(3, Q, 2):
    if not prime[i] and not prime[(i+1)//2]:
        like2017[i] += 1
for i in range(3, Q):
    like2017[i] += like2017[i-1]

for i in range(q):
    print(like2017[lr[i][1]] - like2017[lr[i][0]-1])

Submission status: Accepted

Solution code:
def primes(max_number):
    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(100000))
A = [0]*100002
for p in P:
    if (p+1)//2 in P:
        A[p] += 1
from itertools import accumulate as acc
A = list(acc(A))

q = int(input())
Q = [list(map(int,input().split())) for _ in range(q)]
for i in range(q):
    print(A[Q[i][1]]-A[Q[i][0]-1])

Submission status: Accepted

Solution code:
from math import sqrt

n=100001
prime=[1 for i in range(n)]
prime[0]=0
prime[1]=0
for i in range(2,int(sqrt(n))):
    if prime[i]:
        j=0
        while i*(j+2)<n:
            prime[i*(j+2)]=0
            j+=1

resemble=[0 for i in range(n)]
for i in range(3,n):
    if i%2:
        if prime[i] and prime[int((i+1)/2)]:
            resemble[i]+=1
    resemble[i]+=resemble[i-1]

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