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:
from itertools import accumulate
def eratosthenes(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
                
    return prime_list
n = 100000
prime_list = set(eratosthenes(n))
a = []
for i in range(n):
    if i in prime_list and (i+1) // 2 in prime_list:
        a.append(1)
    else:
        a.append(0)
a = list(accumulate(a))
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(a[r]-a[l-1])

Submission status: Accepted

Solution code:
NUM = 10**5
prime = [True]*(NUM+1)
for i in range(2, int(NUM**0.5)+1):
    if not prime[i]:
        continue
    j = i*2
    while j <= NUM:
        prime[j] = False
        j += i

S = [0]*(NUM+1)
for i in range(3, NUM+1, 2):
    if prime[(i+1)//2] and prime[i]:
        S[i] = S[i-2] + 1
    else:
        S[i] = S[i-2]

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

Submission status: Accepted

Solution code:
N = 10 ** 5
D = [0] * (N + 1)
for i in range(2, N + 1):
  if(D[i] == 0):
    for j in range(i, N + 1, i):
      if(D[j] == 0):
        D[j] = i

T = [0] * (N + 1)
for i in range(3, N, 2):
  if(D[i] == i and D[i + 1] == 2 and D[(i + 1) // 2] == (i + 1) // 2):
    T[i] = 1
S = [0] * (N + 1)

for i in range(N):
  S[i + 1] = S[i] + T[i + 1]

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

Submission status: Accepted

Solution code:

import math
N=int(input())
S=[0]*100010
n=110000
count=0
isprime=[True]*(n+1)
isprime[0]=False
isprime[1]=False
for i in range(2,int(math.sqrt(n))+1):
    if isprime[i]==True:
        j=i+i
        while j<=n:
            isprime[j] =False
            j=j+i

for i in range(2,100010):
    if isprime[i]==True:
        if isprime[(i+1)//2]==True:
            count+=1
    
    S[i]=count
        
                
    

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def Eratosthenes(n):
    from math import sqrt
    res = [True] * (n+1)
    res[0] = False
    res[1] = False
    
    for i in range(2,int(sqrt(n))+1):
        if res[i]:
            for j in range(2*i,n+1,i):
                res[j] = False
    return res

class BIT():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    max_num = 100000
    Q = I()
    S = Eratosthenes(max_num)
    bit = BIT(max_num)
    
    #bitの初期化
    for a in range(1,max_num, 2):
        b = (a+1) // 2
        if S[a] and S[b]:
            bit.add(a, 1)
    
    #queryの処理
    
    for q in range(Q):
        l, r = MI()
        print(bit.sum(r)-bit.sum(l-1))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
q = int(input())
a = [0] * (10 ** 5)
for i in range(1, 10 ** 5, 2):
    if (i + 1) // 2 % 2 == 0:
        pass
    else:
        for j in range(2, int((i)**(1 / 2)) + 1):
            if i % j == 0:
                break
        else:
            k = (i + 1) // 2
            for j in range(2, int((k)**(1 / 2)) + 1):
                if k % j == 0:
                    break
            else:
                a[i] = 1

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

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

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
import numpy as np
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

# nまでの自然数が素数かどうかを表すリストを返す
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime


def main():
    Q = ii()
    l, r = i2(Q)
    m = max(r)

    dp = [0]*(m+1)
    check = makePrimeChecker(m)

    for i in range(1, m+1):
        if check[i] and check[(i+1)//2]:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]

    for ll, rr in zip(l, r):
        print(dp[rr]-dp[ll-1])




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def like2017(x):
  if isprime[x]:
    if isprime[(x+1)//2]:
      return True
  return False

n=108000
isprime=[True]*(n+1)
isprime[0]=isprime[1]=False
for i in range(2,n+1):
  if isprime[i]:
    for j in range(i*i,n+1,i):
      isprime[j]=False
cum=[]
cum.append(like2017(0))
for i in range(1,n+1):
  tmp=0
  if isprime[i]:
    if isprime[(i+1)//2]:
      tmp=1
  cum.append(cum[-1]+tmp)
#print(cum)
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  print(cum[r]-cum[l-1])

Submission status: Accepted

Solution code:
from numpy import *
A = (10**5+1)*[1]
B = (10**5+1)*[0]

for i in range(2,int(10**2.5)+1):
  if A[i]==1:
    for j in range(2*i,10**5+1,i):
      A[j] = 0

for n in range(3,10**5+1):
  if A[n] and A[(n+1)//2]:
    B[n]+=1

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

Submission status: Accepted

Solution code:
def prime_table(n):
    prime = [True]*(n+1)
    prime[0], prime[1] = False, False
    for i in range(2, n+1):
        if not prime[i]: continue
        j = 2*i
        while j <= n:
            prime[j] = False
            j += i
    return prime
N = 10**5
pt = prime_table(N)
cum = [0]*(N+1)
for i in range(1, N+1, 2):
    if pt[i] and pt[(i+1)//2]:
        cum[i] = 1
for i in range(1, N+1):
    cum[i] += cum[i-1]
Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cum[r]-cum[l-1])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
def prime_table(n):
    prime = [True]*(n+1)
    prime[0], prime[1] = False, False
    i = 2
    while i*i <= n:
        if not prime[i]:
            i += 1
            continue
        j = 2*i
        while j <= n:
            prime[j] = False
            j += i
        i += 1
    return prime
N = 10**5
pt = prime_table(N)
cum = [0]*(N+1)
for i in range(1, N+1, 2):
    if pt[i] and pt[(i+1)//2]:
        cum[i] = 1
for i in range(1, N+1):
    cum[i] += cum[i-1]
Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cum[r]-cum[l-1])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
def prime_table(n):
    arr = [True]*(n+1)
    arr[0], arr[1] = False, False
    for i in range(2, N+1):
        if not arr[i]: continue
        j = 2*i
        while j <= n:
            arr[j] = False
            j += i
    return arr
N = 10**5
pt = prime_table(N)
cum = [0]*(N+1)
for i in range(1, N+1, 2):
    if pt[i] and pt[(i+1)//2]:
        cum[i] = 1
for i in range(1, N+1):
    cum[i] += cum[i-1]
Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cum[r]-cum[l-1])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
ALL = []
cnt = 0
import math
def decide_sosuu(n):
    if n <= 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
    return True
for i in range(1,int((10**5)/2+2)):
    if decide_sosuu(i):
        if decide_sosuu((i*2)-1):
            cnt += 1
            ALL.append(cnt)
        else:
            ALL.append(cnt)
    else:
        ALL.append(cnt)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        print(ALL[int(r/2)])
    else:
        print(ALL[int(r/2)] -ALL[int(l/2)-1])

Submission status: Accepted

Solution code:
from math import floor, sqrt
if __name__ == "__main__":
    Q = int(input())
    acc = [0]*(10**5+1)
    primes = set([2])
    for i in range(3,10**5+1):
        fl = True
        for j in range(2, floor(sqrt(i))+1):
            if i % j == 0:
                fl = False
                break
        acc[i] = acc[i-1]
        if fl:
            primes.add(i)
            if (i+1)//2 in primes:
                acc[i] += 1
    for q in range(Q):
        l, r = map(int,input().split())
        print(acc[r]-acc[l-1])

Submission status: Accepted

Solution code:
#クエリにO(1)で返すためのテーブルを用意
import numpy as np
MAX = int(10e5+1)
List = list(range(2,MAX))
P = []
while len(List) > 0:
    p = List[0]
    if p >= np.sqrt(MAX): break
    P.append(p)
    List = [x for x in List if x % p != 0]
P = set(P+List)

Ans = [0] * MAX
cnt = 0
for i in range(1,MAX):
    if i in P and (i+1)//2 in P:
        cnt += 1
    Ans[i] = cnt

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

Submission status: Accepted

Solution code:
# D - 2017-like Number (hint)
import math
Q = int(input())
lr = []
for _ in range(Q):
    l,r = map(int,input().split())
    lr.append((l,r))

# iが素数なら Primes[i] = 1
Primes = [1]*((10**5)+1)
Primes[0],Primes[1] = 0,0

for i in range(2,10**5+1):
    if Primes[i] == 0:
        continue
    M = int(math.sqrt(i))+1 
    for j in range(2,M):
        if i%j == 0:
            Primes[i] = 0
            break
    else:
        for k in range(i*2,(10**5)+1,i):
            Primes[k] = 0

like2017 = [0]*(10**5+1)
for x in range(10**5+1):
    if Primes[x] == 1 and Primes[(x+1)//2] == 1:
        like2017[x] = 1

# 累積和
s = [0]*(len(like2017)+1)
for a in range(len(like2017)):
    s[a+1] = s[a] + like2017[a]

for l,r in lr:
    ans = s[r+1] - s[l]
    print(ans)

Submission status: Accepted

Solution code:
import sys


def like2017(N):

    D = [True] * (N + 1)
    L = [0] * (N + 1)

    D[0] = False
    D[1] = False

    for n in range(2, N + 1):
        if not D[n]:
            continue

        for k in range(2, N // n + 1):
            D[k * n] = False

    cnt = 0
    for n in range(1, N + 1):
        if D[n] and D[(n + 1) // 2] and n % 2 == 1:
            cnt += 1
        L[n] = cnt

    return L


def main():
    Q = int(sys.stdin.readline().rstrip())  # クエリ数

    L = like2017(10**5)

    for _ in range(Q):
        l, r = map(int, sys.stdin.readline().rstrip().split())
        print(L[r] - L[l - 1])


main()

Submission status: Accepted

Solution code:
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return 0
    return 1


sl = [0, 0]
for j in range(2, 10 ** 5 + 1):
    if j % 2 == 0:
        sl.append(sl[j - 1])
    elif is_prime(j) == 1 and is_prime((j + 1) // 2) == 1:
        sl.append(sl[j - 1] + 1)
    else:
        sl.append(sl[j - 1])

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

Submission status: Accepted

Solution code:
S = set()
L = [True]*(10**5+1)
L[0] = False
L[1] = False
for i in range(2, 10**5+1):
    if L[i]:
        S.add(i)
        for j in range(i*2, 10**5+1, i):
            L[j] = False


def prime(n):
    return n in S


M = [0]*(5*10**4+1)
for i in range(1, 5*10**4+1):
    m = 2*i-1
    n = i
    M[i] = M[i-1]+(prime(m) & prime(n))

Q = int(input())
ans = [0]*Q
for _ in range(Q):
    l, r = list(map(int, input().split()))
    i = (l+1)//2
    j = (r+1)//2
    ans[_] = M[j]-M[i-1]
for _ in range(Q):
    print(ans[_])

Submission status: Accepted

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

#def numsearch(list):
    #for i in list:
        #print(i)
        #if (i+1)/2 not in list:
            #list.remove(i)
    #return list

def main():
    Q = int(input())
    list = seachPrimeNum(100000)
    #フラグを立てるよ
    check = [0]*100001
    primeCheck = [0]*100001
    for i in list:
        primeCheck[i] = 1
    for i in list:
        if i == 2:
            continue
        tmp = int((i+1)/2)
        if primeCheck[tmp] == 1:
            check[i] = 1
    #答えを求めるための累積和
    c = [0]*100001
    c[0] = 0
    for i in range(1,100001,1):
        #print(i)
        if check[i] == 1:
            c[i] = c[i-1]+1
        else:
            c[i] = c[i-1]
    #print(c)
    for i in range(Q):
        l,r = map(int,input().split())
        print(c[r]-c[l-1])

main()

Submission status: Accepted

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

N=10**5
A=[1]*(N+1)
A[0]=A[1]=0
i=2
while i*2<=N:
    if A[i]:
        j=2
        while i*j<=N:
            A[i*j]=0
            j+=1
    i+=1

S=[0]*(N+1)
for i in range(N+1):
    if A[i] and A[(i+1)//2]:
        S[i]=1
    S[i]+=S[i-1]

for l,r in lr:
    print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
import math
N = 10**5
Q = int(input())

primes = set()
visited = set()
for i in range(2,N+1):
  if i in visited: continue
  primes.add(i)
  j = i
  while j <= N:
    visited.add(j)
    j += i

C = [0 for _ in range(N+1)]
ct = 0
for x in range(3,N+1,2):
  if x in primes and (x+1)//2 in primes:
    ct += 1
  C[x] = ct
  
#print(primes)
#print(C)

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

Submission status: Accepted

Solution code:
from itertools import accumulate

q, *lr = map(int, open(0).read().split())

p = [True] * 100010
p[0] = False
p[1] = False
i = 2
while i <= 100005:
    if p[i]:
        j = i * 2
        while j <= 100005:
            p[j] = False
            j += i
    i += 1

s = [0] * 100010
for i in range(3, 100005, 2):
    if p[i] and p[(i + 2) // 2]:
        s[i] += 1
s = tuple(accumulate(s))

for l, r in zip(*[iter(lr)] * 2):
    print(s[r] - s[l - 1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

Q = int(input())

primes = set()
not_p = set()
for i in range(2, 10**5 + 1):
# for i in range(2, 10 + 1):
    if i not in not_p:
        primes.add(i)
        for j in range(i+i, 10**5+1, i):
        # for j in range(i+i, 10+1, i):
            not_p.add(j)
# print(primes)
# print(not_p)

acum = [0 for _ in range(10**5+1)]
for i in range(3, 10**5+1, 2):
# for i in range(3, 10, 2):
    if i in primes and ((i+1) // 2) in primes:
        # print(i, "like2017")
        acum[i] += 1
    acum[i] += acum[i-2]
# print(acum[:10])

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

Submission status: Accepted

Solution code:
import itertools
import copy
q=int(input())
qr=[list(map(int,input().split())) for i in range(q)]
sosu=[1]*(10**5+1)
sosu[0]=0
sosu[1]=0
k=2
while k<(10**5+1)**0.5+1:
  for i in range(2*k,10**5+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
    
n=[0]*(10**5+1)
for i in range(1,len(sosu)):
  if i%2==1 and sosu[i]==1 and sosu[(i+1)//2]==1:
    n[i]=1
ans=list(itertools.accumulate(n))
for i in range(q):
  print(ans[qr[i][1]]-ans[qr[i][0]-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

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


like_numbers = [0] * (10 ** 6)
for p in primes(10 ** 5):
    like_numbers[p * 2 - 1] += 1
    like_numbers[p] += 1

like_numbers = [1 if i == 2 else 0 for i in like_numbers]
like_numbers = list(accumulate(like_numbers))

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

Submission status: Accepted

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

# In[18]:


import itertools


# In[19]:


def sieve(x):
    p = []
    b = [1]*(x+1)
    for i in range(2,x+1):
        if b[i]:
            p += [i]
            for j in range(2*i,x+1,i):
                b[j] = 0
    return p
p=sieve(10**5)


# In[27]:


s = set(i for i in p if i<5*10**4)
l = [0]*(10**5)
for i in p[1:]:
    if i//2 + 1 in s:
        l[i] = 1
S = list(itertools.accumulate(l))


# In[30]:


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


# In[ ]:

Submission status: Accepted

Solution code:
import sys,math
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n))+1,n+1):
        if A[i] == 1:
            prime_list.append(i)
    return prime_list,A


prime_list,A = sieve_of_eratosthenes(10**5)

like_2017 = [0]*(10**5+1)
for p in prime_list:
    if p == 2:
        continue
    else:
        if A[(p+1)//2] == 1:
            like_2017[p] = 1

from itertools import accumulate

C = list(accumulate(like_2017))

Q = I()
for i in range(Q):
    l,r = MI()
    print(C[r]-C[l-1])

Submission status: Accepted

Solution code:
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

pr = primes(100000)
d=[0]*100001
ans=[0]*100001

for j in pr:
    d[j]=1

for k in pr:
    tmp = (k+1)//2
    if d[tmp]==1:
        ans[k]=1

import numpy as np
cum = np.cumsum(ans)

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

Submission status: Accepted

Solution code:
def cal_primes(N):
    candidate = [*range(2, N+1)]
    primes = []

    while candidate[0]**2 <= N:
        primes.append(candidate[0])
        candidate = [*filter(lambda x: x % candidate[0] != 0, candidate)]
    
    primes.extend(candidate)
    return primes

Q = int(input())
primes = set(cal_primes(10**5))
# print(primes)
res = [0] * (10**5+1)
for i in range(1,10**5+1):
    #print(i)
    if i%2==1 and i in primes and (i+1)//2 in primes:
        res[i] = res[i-1] + 1
    else:
        res[i] = res[i-1]
#print(res)
for i in range(Q):
    l, r = map(int, input().split())
    print(res[r]-res[l-1])

Submission status: Accepted

Solution code:
P = [1 for _ in range(10**5)]
P[0]=0
P[1]=0
for i in range(2,int((10**5)**0.5)+1):
    for j in range(i*i,10**5,i):
        P[j]=0
Q = []
for i in range(3,10**5,2):
    if P[i]==1 and P[(i+1)//2]==1:
        Q.append(i)
A = [0 for _ in range(10**5+1)]
for q in Q:
    A[q] = 1
for i in range(1,10**5+1):
    A[i] += A[i-1]
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    print(A[r]-A[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate


def LI():
    return list(map(int, input().split()))


Q = int(input())
n = 10**5
sosu = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    sosu.difference_update(range(i*2, n+1, i))
xlist = [0]*(10**5+1)
for i in range(1, 10**5+1, 2):
    if i in sosu:
        if (i+1)//2 in sosu:
            xlist[i] = 1
Xsum = list(accumulate(xlist))
for _ in range(Q):
    L, R = LI()
    ans = Xsum[R]-Xsum[L-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

s = set()
for i in range(2, 10**5+5):
    if i in s:
        continue
    cnt = 2
    while i*cnt<=10**5+5:
        s.add(i*cnt)
        cnt += 1

from itertools import accumulate

lis = [0]*(10**5+5)
for i in range(3, 10**5+5, 2):
    if not i in s and not (i+1)//2 in s:
        lis[i] = 1

lis = list(accumulate(lis))
Q = int(input())
for _ in range(Q):
    l, r = mapint()
    print(lis[r]-lis[l-1])

Submission status: Accepted

Solution code:
q = int(input())

p = [True] * 100010
s = [0] * 100010
p[0] = False
p[1] = False
i = 2
while i <= 100005:
    if p[i]:
        j = i * 2
        while j <= 100005:
            p[j] = False
            j += i
    i += 1


for i in range(100005):
    if i & 1 and p[i] and p[(i + 1) // 2]:
        s[i] += 1
for i in range(100005):
    s[i + 1] += s[i]

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

Submission status: Accepted

Solution code:
q=int(input())
query=[list(map(int,input().split())) for _ in range(q)]
def factorize(n):
    if n==0:
        return 0
    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 len(a)
s=[0]*100001 #s[i]==1:iが素数
for i in range(100001):
    s[i]=factorize(i)
j=[0]*100001
count=0
for i in range(100000):
    if s[i]==1:
        if s[(i+1)//2]==1:
            count+=1
            j[i]=count
        else:
            j[i]=count
    else:
        j[i]=count
for l,r in query:
    print(j[r]-j[l-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    q = int(input())
    primes = set()
    nums = set()
    for i in range(2, 10 ** 5 + 1):
        if is_prime(i):
            primes.add(i)
            if (i + 1) // 2 in primes:
                nums.add(i)

    cnt = [0]
    for i in range(1, 10 ** 5 + 1):
        op = 1 if i in nums else 0
        cnt.append(cnt[-1] + op)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def prime(p):
    primeFlag = True
    if p == 1:
        primeFlag = False
    for i in range(2,(int(p**0.5)+1)):
        if p%i==0:
            primeFlag = False
            break
    if primeFlag:
        return True
    else:
        return False
    
Q = int(input())

memo = [0]*100001

for i in range(2,100001):
    first = prime(i)
    second = prime((i+1)//2)
    if first and second:
        memo[i] = 1

for i in range(1,100001):
    memo[i] = memo[i-1]+memo[i]

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

Submission status: Accepted

Solution code:
from itertools import accumulate
n = 10**5 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


def like_2017(n):
    return n in primes and (n + 1) // 2 in primes


result = [0] * 10**5
for i in range(1, 10**5 + 1, 2):
    result[i] = like_2017(i)


cumsum = list(accumulate(result))

q = int(input())

for _ in range(q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[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]]

sums = [0,0,0]
curr_sum = 0
ps = primes(10**3)
pset = set(ps)
for i in range(3,10**5+1):
    for p in ps:
        if i%p == 0 and i not in pset:
            break
        if ((i+1)//2)%p == 0 and ((i+1)//2) not in pset:
            break
    else:
        curr_sum += 1
        # print(i)
    sums.append(curr_sum)
    

q = int(input())
ansl = []
for _ in range(q):
    l,r = map(int, input().split())
    ans = sums[r] - sums[l-1]
    ansl.append(ans)

for a in ansl: print(a)

# print(sums[:54])

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5) #ルートn以上で割れることはない
    data = [i + 1 for i in range(2, n, 2)] #最初から3スタートの奇数にしておく
    while True:
        p = data[0]
        if limit < p: #ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。
            return prime + data
        prime.append(p) #ここで一番最初に取り出した素数を加える。
        data = [e for e in data if e % p != 0] #残りでその素数で割れない数字を取得。

MAX = pow(10,5)+10
A = get_sieve_of_eratosthenes(MAX)
A = set(A)
S = [0]
for i in range(1,MAX):
  if i in A and (i+1)%2 == 0 and (i+2)//2 in A:
    temp = S[-1]+1
  else:
    temp = S[-1]
  S.append(temp)
Q = int(input())
for i in range(Q):
  l,r = map(int,input().split())
  ans = S[r]-S[l-1]
  print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


import math


def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n))+1,n+1):
        if A[i] == 1:
            prime_list.append(i)
    return prime_list,A


prime_list,A = sieve_of_eratosthenes(10**5)

B = [0]*(10**5+1)
for p in prime_list:
    if p == 2:
        continue
    else:
        if A[(p+1)//2] == 1:
            B[p] = 1

from itertools import accumulate

C = list(accumulate(B))

Q = I()
for i in range(Q):
    l,r = MI()
    print(C[r]-C[l-1])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
a = [0] * 100100
for i in range(1,100010):
    tmp = 0
    if is_prime(i) and is_prime((i+1)//2):
        tmp = 1
    a[i] = a[i-1] + tmp
q = inp()
for _ in range(q):
    l,r = inpl()
    print(a[r] - a[l-1])

Submission status: Accepted

Solution code:
def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    return True

def is_2017(num):
    temp = (num + 1) // 2
    if isPrime(num) and isPrime(temp):
        return True
    else:
        return False

if __name__ == "__main__":
    
    Q = int(input())
    
    is_2017_list = [0] * (10**5 + 1)
    count = 0
    for i in range(1, 10**5):
        if is_2017(i):
            count += 1
            is_2017_list[i] = count
            
        else:
            is_2017_list[i] = count

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

Submission status: Accepted

Solution code:
def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    return True

def is_2017(num):
    temp = (num + 1) // 2
    if isPrime(num) and isPrime(temp):
        return True
    else:
        return False

if __name__ == "__main__":
    
    is_2017_list = [0] * (10**5 + 1)
    count = 0
    for i in range(1, 10**5):
        if is_2017(i):
            count += 1
            is_2017_list[i] = count
            
        else:
            is_2017_list[i] = count

    Q = int(input())

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