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:
import math

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

all=[0]+[0]*(10**5+1)
for i in range(3,10**5):
    if is_prime((i)) and is_prime((i+1)//2) :
        all[i]=all[i-1]+1
    else:
        all[i]=all[i-1]



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

Submission status: Accepted

Solution code:
Q = int(input())
MAX = 10**5 + 10
def makePrimeChecker(n):
    """
    エラトステネスの篩.
    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

is_prime = makePrimeChecker(MAX)
cum_sim = [0] * (MAX)
for i in range(1, MAX):
    if i % 2 == 0:
        cum_sim[i] = cum_sim[i-1]
    else:
        if is_prime[i] and is_prime[(i+1)//2]:
            cum_sim[i] = cum_sim[i-1] + 1
        else:
            cum_sim[i] = cum_sim[i-1]
for q in range(Q):
    l, r = map(int, input().split())
    print(cum_sim[r] - cum_sim[l-1])

Submission status: Accepted

Solution code:
prime = [0,0] + [1]*(10**5-1) #0,1は素数でない
for x in range(2, 5 * 10**2 + 1):
    if prime[x]:
        for i in range(2, 10**5 // x + 1):
            prime[x*i] = 0

islike2017 = [0]*(10**5+1)
cnt = 0
for z in range(2, 10**5 + 1):
    if prime[z] and prime[(z+1)//2]:
        cnt += 1
    islike2017[z] = cnt

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

Submission status: Accepted

Solution code:
def sieve(x):
  p=[]
  b=[1]*x
  for i in range(2,x):
    if b[i]:
      p+=[i]
      for j in range(2*i,x,i): b[j]=0
  return p
p=sieve(10**5+1)
s=set(i for i in p if i<5e4)
l=[0]*(10**5)
for i in p[1:]:
  if i//2+1 in s:
    l[i]=1
from itertools import *
S=[*accumulate(l)]
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
def sb(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
num=[0]*(10**5+1)
num2=[0]*(10**5+1)
cnt=[0]*(10**5+1)
num[2]+=1
for i in range(2,10**5+1):
    if i%2==1:
        n=sb(i)
        if len(n)==1 and n[0][1]==1:
            num[i]+=1
        if num[i]==1 and num[(i+1)//2]==1:
            num2[i]+=1
for i in range(1,len(num2)):
    cnt[i]=cnt[i-1]+num2[i]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

# エラトステネスの篩
def eratosthenes(n): 
    prime_list = []
    num_list=[i for i in range(2, n+1)] # 2以上n以下の整数を並べる
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0] # 倍数をふるい落とす

max_lr = 100000
er_list = eratosthenes(max_lr)

count = [0] * max_lr
for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1

# 累積和            
count = list(accumulate(count)) 

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

def eratosthenes(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

def 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)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

        
Q = int(input())
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
    
max_r = max(r)+1
er_list = eratosthenes(max_r)
count = [0] * max_r


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
for i in range(Q):
    print(count[r[i]] - count[l[i]-1])

Submission status: Accepted

Solution code:
from itertools import accumulate


# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print(check[R[i] + 1] - check[L[i]])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate


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

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

    return 1


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print(check[R[i] - min_L + 1] - check[L[i] - min_L])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = [0]*100000

j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count[i] = 1 
            
count = list(accumulate(count))
            
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import math

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = [0]*100000
j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count[i] = 1 
            
for i in range(1,len(count)):
    count[i]  = count[i]+count[i-1]
    
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import math

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = [0 for i in range(100000)]
j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count[i] = 1 
            
for i in range(1,len(count)):
    count[i]  = count[i]+count[i-1]
    
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import math
def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

ls = eratosthenes(100000)
ls2 = []
count = [0 for i in range(100000)]
j = 0
for i in range(ls[-1]):
    if i == ls[j]:
        j += 1
        if (i+1)//2 in ls:
            count[i] = 1
            
            
for i in range(1,len(count)):
    count[i]  = count[i]+count[i-1]
    
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r]-count[l-1])

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    Q = NI()
    LR = [NLI() for _ in range(Q)]

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

    cumsum = [0 for _ in range((10**5)+10)]
    cnt = 0
    for n in range(1,len(cumsum)):
        cumsum[n] = cumsum[n-1]
        if is_prime(n):
            if is_prime((n+1)//2):
                cumsum[n] += 1
    
    for q in range(Q):
        print(cumsum[LR[q][1]] - cumsum[LR[q][0]-1])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mx = 100005
q = int(input())

primes = [True for x in range(mx)]
primes[0] = False
primes[1] = False
for i in range(2, mx):
    if primes[i]:
        for j in range(i*i, mx, i):
            primes[j] = False

dp = [0 for x in range(mx)]
for i in range(1, mx):
    if i % 2 == 0:
        dp[i] = dp[i-1]
    else:
        if primes[i] and primes[(i+1)//2]:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]

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

Submission status: Accepted

Solution code:
def Sieve_of_Eratosthenes(N,mode=False):
    """Nまでのエラトステネスの篩を実行

    N:自然数
    mode:False->素数のリスト,True->素数かどうかのリスト
    (False->[2,3,5,...],True->[False,False,True,True,False,True,...])
    """

    T=[True]*(N+1)
    T[0]=T[1]=0
    a=2
    while a*a<=N:
        if T[a]:
            b=a*a
            while b<=N:
                T[b]=False
                b+=a
        a+=1

    if mode:
        return T
    else:
        return [k for k in range(N+1) if T[k]]
#=====================================================
N_max=10**5
Q=int(input())

P=Sieve_of_Eratosthenes(N_max,True)
Y=[0]*(N_max+1)
for a in range(1,N_max+1):
    Y[a]=Y[a-1]+((a%2==1) and P[a] and P[(a+1)//2])

X=[0]*Q
for k in range(Q):
    l,r=map(int,input().split())
    X[k]=Y[r]-Y[l-1]

print("\n".join(map(str,X)))

Submission status: Accepted

Solution code:
MAX = 10 ** 5 + 1
f = [True] * (MAX)
c = [0] * (MAX + 1)
for i in range(2, MAX):
    if f[i]:
        for j in range(i + i, MAX, i):
            f[j] = False
for i in range(3, MAX, 2):
    if f[i] and f[(i + 1) // 2]:
        c[i] += 1
for i in range(3, MAX):
    c[i] += c[i - 1]

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

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
    
    like=[False]*(n+1)
    for i in range(1,n+1,2):
        if(is_prime[i]==False):
            continue
        else:
            if(is_prime[int((i+1)/2)]==True):
                like[i]=True
            
    return  like
    #return [i for i in range(n + 1) if is_prime[i]]
q=int(input())
table=primes(10**5+10)
accum=[0]
for i in range(1,10**5+5):
        if(table[i]==True):
            accum.append(accum[i-1]+1)
        else:
            accum.append(accum[i-1])
for i in range(q):
    l,r=map(int,input().split())
    print(accum[r]-accum[l-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
Q = int(input())
prime = [0] + [1] * 10**5
prime[1] = 0
c = [0]
for i in range(1, 10**5 + 1):
    if prime[i]:
        c.append(c[-1] + prime[(i + 1) // 2])
        if i <= 10**2.5:
            for j in range(2, 10**5 // i+1):
                prime[j * i] = 0
    else:
        c.append(c[-1])
for i in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l-1])

Submission status: Accepted

Solution code:
import math
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
Q = int(input())
cnt = [0]*(10**5+1)
for i in range(1,10**5+1):
    if i % 2 == 0:
        cnt[i] = cnt[i-1]
        continue
    if is_prime(i) and is_prime((i+1)//2):
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]
for _ in range(Q):
    l, r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
import copy
import math
c=[0]*(10**5+1)
for n in range(2,10**5+1):
  for k in range(2, int(math.sqrt(n))+1):
    if n%k==0:
      break
  else:
    c[n]=1
cc=[0]*(10**5+1)
for n in range(1,10**5+1,2):
  if c[n] and c[(n+1)//2]:
    cc[n]=1
#print(*c[:100])
for i in range(1,10**5+1):
  cc[i] += cc[i-1]
#print(*c[:100])
#print(*[(i,cc[i]) for i in range(1,54)])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(cc[r]-cc[l-1])

Submission status: Accepted

Solution code:
import math

def is_prime(x):
  if x <= 0 or x%1 != 0:
    return False
  elif x == 1:
    return False
  elif x == 2:
    return True
  elif x%2 == 0:
    return False
  else:
    for i in range(3, int(math.sqrt(x)//1)+1, 2):
      if x%i == 0:
        return False
    return True

S = [0] * (10**5+1)
for i in range(1, 10**5+1):
  if is_prime(i) and is_prime((i+1)/2):
    S[i] += 1
  S[i] += S[i-1]

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

Submission status: Accepted

Solution code:
Q = int(input())

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


def primes(max_r):
    is_prime = [True] * (max_r + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(max_r**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, max_r + 1, i):
            is_prime[j] = False
    return [i for i in range(max_r + 1) if is_prime[i] and is_prime[(i+1)//2]]


max_r = max(R)
ps = primes(max_r)

S = [0]
for i in range(1, max_r+1):
    if i in ps:
        S.append(S[i-1]+1)
    else:
        S.append(S[i-1])


for i in range(Q):
    print(S[R[i]] - S[L[i]-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

Q = int(input())

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


def primes(max_r):
    is_prime = [True] * (max_r + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(max_r**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, max_r + 1, i):
            is_prime[j] = False
    return [i for i in range(max_r + 1) if is_prime[i] and is_prime[(i+1)//2]]


max_r = max(R)
ps = primes(max_r)

S = [0]
for i in range(1, max_r+1):
    if i in ps:
        S.append(S[i-1]+1)
    else:
        S.append(S[i-1])


for i in range(Q):
    print(S[R[i]] - S[L[i]-1])

Submission status: Accepted

Solution code:
import math


def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


q = int(input())
l, r = [], []
for _ in range(q):
    _lr = list(map(int, input().split()))
    l.append(_lr[0])
    r.append(_lr[1])
N = 10 ** 5 + 1

prime_list = eratosthenes(N)
prime_flag = [False for _ in range(10 ** 5 + 2)]
like_2017 = [0 for _ in range(10 ** 5 + 2)]
like_cnt = 0

for p in prime_list:
    prime_flag[p] = True

for i in range(10 ** 5 + 2):
    if prime_flag[(i + 1) // 2] and prime_flag[i]:
        like_cnt += 1
    like_2017[i] = like_cnt

for i in range(q):
    print(like_2017[r[i]] - like_2017[l[i] - 1])

Submission status: Accepted

Solution code:
import math
Q = int(input())

li = [0]
cnt = 0
for i in range(3, 10**5+1, 2):
  flag = True
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      flag = False
  if flag:
    for j in range(2, int(math.sqrt((i+1)//2)+1)):
      if ((i+1)//2) % j == 0:
        flag = False
  if flag:
    cnt += 1
  li.append(cnt)
  
for i in range(Q):
  l, r = map(int, input().split())
  if l == 1:
    ans = li[r//2]
  else:
    ans = li[r//2] - li[l//2-1]
  print(ans)

Submission status: Accepted

Solution code:
import math
Q = int(input())

li = [0]
cnt = 0
for i in range(3, 10**5+1, 2):
  flag = True
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      flag = False
  if flag:
    for j in range(2, int(math.sqrt((i+1)//2)+1)):
      if ((i+1)//2) % j == 0:
        flag = False
  if flag:
    cnt += 1
  li.append(cnt)
  
for i in range(Q):
  l, r = map(int, input().split())
  if l == 1:
    ans = li[r//2]
  else:
    ans = li[r//2] - li[l//2-1]
  print(ans)

Submission status: Accepted

Solution code:
import math
Q = int(input())

li = [0]
cnt = 0
for i in range(3, 10**5+1, 2):
  flag = True
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      flag = False
  for j in range(2, int(math.sqrt((i+1)//2)+1)):
    if ((i+1)//2) % j == 0:
      flag = False
  if flag:
    cnt += 1
  li.append(cnt)
  
for i in range(Q):
  l, r = map(int, input().split())
  if l == 1:
    ans = li[r//2]
  else:
    ans = li[r//2] - li[l//2-1]
  print(ans)

Submission status: Accepted

Solution code:
q = int(input())
Q = 10**5+1
is_prime = [1] * (Q+1)
is_prime[0],is_prime[1] = 0,0
for i in range(2,int(Q*0.5)+1):
    if is_prime[i]:
        product = i*2
        while product <= Q:
            is_prime[product] = 0
            product += i
is_2017_like = [0] * (Q+1)
is_2017_like_csum = [0] * (Q+1)
now = 0
for i in range(2,Q+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        is_2017_like[i] = 1
        now += 1
    is_2017_like_csum[i] = now
ans_ls = [0] * q
for i in range(q):
    l,r = map(int,input().split())
    if l >= 1:
        ans_ls[i] = is_2017_like_csum[r] - is_2017_like_csum[l-1]
    else:
        ans_ls[i] = is_2017_like_csum[r]
for i in range(q):
    print(ans_ls[i])

Submission status: Accepted

Solution code:
import math
import itertools

def get_prime(n):
    if n<=1:
      return []
    prime=[2]
    limit=int(math.sqrt(n))
    
    data=[i+1 for i in range(2,n,2)]
    while limit>data[0]:
      prime.append(data[0])
      
      data=[j for j in data if j % data[0]!=0]
      
    return prime+data

xx=get_prime(100000)

xxx=[False]*100001

for i in xx:
  xxx[i]=True

xxxx=[False]*100001

for i in xx:
  xxxx[i]=True

for i in range(1,100001):
  if xxx[i]==True:
    if xxxx[(i+1)//2]==False:
      xxx[i]=False

q=int(input())

for i in range(100001):
  if xxx[i]==True:
    xxx[i]=1
  else:
    xxx[i]=0
    
xxx=list(itertools.accumulate(xxx))
    

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def read():
    Q = int(input().strip())
    LR = []
    for i in range(Q):
        l, r = map(int, input().strip().split())
        LR.append((l, r))
    return Q, LR


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return is_prime


def solve(Q, LR, N=10**5+1):
    primes = sieve(N)
    S = [0 for i in range(N+2)]
    for i in range(3, N+2, 2):
        d = 1 if primes[i] & primes[(i+1)//2] else 0
        S[i] = S[i-2] + d
    for l, r in LR:
        ans = S[r] - S[l-2]
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
#-----------------------------------
#リストera_list[n]を返す
#0～ｎの各インデックスが素数であれば1、そうでなければ0
#ex：eratosthenes(10)
#　　→ [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
#-----------------------------------

def eratosthenes(n):
  era_list = [1] * (n + 1)
  era_list[0] = 0; era_list[1] = 0
  
  for i in range(2,n+1):
    if era_list[i] == 0:
      continue
    else:
      j = i + i
      while j <= n:
        era_list[j] = 0
        j += i
        
  return era_list

Q = int(input())
PN = eratosthenes(100001)
TF = [0] * 100001

for i in range(1,100001,2):
  if PN[i] == 1 and PN[int((i+1)/2)] == 1:
    TF[i] = 1 + TF[i-2]
  else:
    TF[i] = TF[i-2]
    
for j in range(1,Q+1):
  l,r = map(int, input().split())
  Ans = TF[r] - TF[l-2]
  print(Ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    Q = int(input())

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    mul += 1
        return {i for i in range(sup+1) if primes[i]}
    primes = Eratosthenes(10**5)
    S = [0]*(10**5+1)
    for a in range(2, 10**5+1):
        if a in primes and (a+1)//2 in primes:
            S[a] = 1
        S[a] += S[a-1]

    for _ in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    mul += 1
        return {i for i in range(sup+1) if primes[i]}
    primes = Eratosthenes(10**5)
    S = [0]*(10**5+1)
    for a in range(2, 10**5+1):
        if a in primes and (a+1)//2 in primes:
            S[a] = 1
        S[a] += S[a-1]

    for _ in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

def main():

    Q = int(input())
    ma = 10 ** 5 + 1
    dp = [0] * ma
    dp[2] = 1

    for i in range(3,ma,2):
        if dp[i] == 0:
            dp[i] = 1
            if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
                dp[i] = 2
            for j in range(i * 2,ma,i):
                dp[j] = 3

    ruiseki = [0] * ma

    for i in range(1,ma):
        if dp[i] == 2:
            ruiseki[i] = ruiseki[i-1] + 1
        else:
            ruiseki[i] = ruiseki[i-1]

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

Q = int(readline())

# 10 ** 5までの「2017に似た数」を全て求めておく

fact = [True] * (10 ** 5 + 1)
fact[0] = False
fact[1] = False
like2017 = [0] * (10 ** 5 + 1)
for i in range(2, len(fact)):
  if fact[i]:
    if i % 2 == 1 and fact[(i + 1) // 2]:
      like2017[i] = 1
    for j in range(i * 2, len(fact), i):
      fact[j] = False
        
for i in range(1, len(like2017)):
  like2017[i] += like2017[i - 1]

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

Submission status: Accepted

Solution code:
q = int(input())

# エラストネスの篩
n = 10**5+1
flag = [True]*n
flag[1] = False
for i in range(4, n, 2): flag[i] = False
for i in range(3, int(n**0.5)+1, 2):
  if flag[i]:
    for j in range(i+i, n, i): flag[j] = False

# 2017に似た数の累積和
nums = [0]*n
for i in range(1,n):
  if i%2 == 1:
    if flag[i] and flag[(i+1)//2]: nums[i] = nums[i-1]+1
    else: nums[i] = nums[i-1]
  else: nums[i] = nums[i-1]

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

Submission status: Accepted

Solution code:
q = int(input())

n = 10**5+1
flag = [True]*n
flag[1] = False
for i in range(4, n, 2): flag[i] = False
for i in range(3, int(n**0.5)+1, 2):
  if flag[i]:
    for j in range(i+i, n, i): flag[j] = False

nums = [0]*n
for i in range(1,n):
  if i%2 == 1:
    if flag[i] and flag[(i+1)//2]: nums[i] = nums[i-1]+1
    else: nums[i] = nums[i-1]
  else: nums[i] = nums[i-1]

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

Submission status: Accepted

Solution code:
import sys

read=sys.stdin.read

def main():
  q,*lr=map(int,read().split())
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]
  for l,r in zip(*[iter(lr)]*2):
    print(ans[r]-ans[l-1])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

readline=sys.stdin.readline
read=sys.stdin.read

def main():
  q,*lr=map(int,read().split())
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      ans[i]=1
      #ans[i]=ans[i-1]+1
    #else:
      #ans[i]=ans[i-1]
  
  ans=list(accumulate(ans))
  for l,r in zip(*[iter(lr)]*2):
    print(ans[r]-ans[l-1])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

readline=sys.stdin.readline
read=sys.stdin.read

def main():
  q,*lr=map(int,read().split())
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      #ans[i]=1
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]
  
  #ans=list(accumulate(ans))
  for l,r in zip(*[iter(lr)]*2):
    print(ans[r]-ans[l-1])

if __name__=='__main__':
  main()

Submission status: Accepted

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

def main():
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]

  for e in lr:
    print(ans[e[1]]-ans[e[0]-1])

if __name__=='__main__':
  main()