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 numpy as np
MAXX = 10**5 + 5

isprime = np.ones(MAXX, dtype=bool)
count = np.zeros(MAXX, dtype=int)

#eratosen no furui
isprime[0] = isprime[1] = False
for i in range(2, MAXX):
    if isprime[i]:
        isprime[2*i::i] = False

for i in range(1, MAXX):
    if isprime[i] and isprime[(i+1)>>1]:
        count[i] = 1

#累積和
for i in range(1, MAXX):
    count[i] += count[i-1]

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

Submission status: Accepted

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

#nの素数判定
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

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

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

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

Submission status: Accepted

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

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

prime=[0]*(10**5+1)
prime_lst=get_sieve_of_eratosthenes(10**5)
for i in prime_lst:
    prime[i]+=1

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

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

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

Submission status: Accepted

Solution code:
import bisect

sosu=set()
nums=[1]*(10**5+1)
for i in range(2, 10**5+1):
  if nums[i]==1:
    sosu.add(i)
    j=i
    while j<10**5+1:
      nums[j]=0
      j+=i
      
nums=[x for x in range(3, 2*10**5+1, 2) if x in sosu and (x+1)//2 in sosu]

Q=int(input())
for _ in range(Q):
  l, r=map(int, input().split())
  a=bisect.bisect_left(nums, l)
  b=bisect.bisect_right(nums, r+1)
  print(b-a)

Submission status: Accepted

Solution code:
from itertools import accumulate
Q = int(input())
m = 0
ls = []
for i in range(Q):
    l, r = map(int, input().split())
    m = max(m, max(l, r))
    ls.append((l, r))

def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

a = sieve_eratosthenes(m)
b = [0 for i in range(m+1)]
for i in range(2, m+1):
    if i%2 == 1 and a[i] == 1 and a[(i+1)//2] == 1:
        b[i] = 1
c = list(accumulate(b))
for l, r in ls:
    print(c[r] - c[l-1])

Submission status: Accepted

Solution code:
import sys
# readline = sys.stdin.readline
read = sys.stdin.read
from itertools import accumulate
from copy import deepcopy
def main():
    maxa2 = 10**5
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    p2 = deepcopy(p)
    for i, pe in enumerate(p):
        if pe:
            i2 = ((i + 1) / 2)
            if i2 % 1 != 0:
                p2[i] = False
                continue
            elif not p[int(i2)]:
                p2[i] = False
    p2a = tuple(accumulate(p2))

    q = int(input())
    m = map(int, read().split())
    lr= zip(m, m)
    for l, r in lr:
        print(p2a[r] - p2a[l-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def p(x):
  if x<2:
    return 0
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return 0
  return 1

C=[0]
for i in range(1,10**5+1):
  C.append(C[-1]+(p(i)&p((i+1)//2)))
l,r=0,0
for i in range(int(input())):
  l,r=map(int,input().split())
  print(C[r]-C[l-1])

Submission status: Accepted

Solution code:
import itertools
n=int(input())
d=[list(map(int,input().split())) for i in range(n)]

sosuu=[1 for i in range(10**5+1)]
#sosuuのindexの値が1の時素数とする。
sosuu[0]=0
sosuu[1]=0
for i in range(2,int((10**5+1)**0.5)+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1:
    for j in range(2*i,10**5+1,i):
      sosuu[j]=0
like_n=[]
like_n+=sosuu
#奇数なので、2を削除。
like_n[2]=0
for i in range(3,10**5+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1 and sosuu[(i+1)//2]==0:
    like_n[i]=0
ans= list(itertools.accumulate(like_n))
for ans_d in d:
  print(ans[ans_d[1]]-ans[ans_d[0]-1])

Submission status: Accepted

Solution code:
q=int(input())
el=[True for _ in range(10**5+1)]
el[0]=False
el[1]=False
temp=[0]*(10**5+1)
i=2
while i*i<=10**5+1:
    for j in range(2*i,10**5+1,i): el[j]=False
    i+=1
cnt=0
for i,val in enumerate(el):
    if val and el[(i+1)//2]:
        cnt+=1
    temp[i]=cnt

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

Submission status: Accepted

Solution code:
Q = int(input())

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

primes = sieve_of_erastosthenes(10**5)
likes = []
for i in range(3, 10**5, 2):
    if primes[i] and primes[(i+1)//2]:
        likes.append(i)

from bisect import bisect_left, bisect_right

for _ in range(Q):
    l, r = map(int, input().split())
    print(bisect_right(likes, r) - bisect_left(likes, l))

Submission status: Accepted

Solution code:
from itertools import accumulate


def eratos(N):
    is_prime = [1]*(N+1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(N**0.5)+1):
        if is_prime[i]:
            for j in range(i**2, N+1, i):
                is_prime[j] = 0
    return is_prime


inf = 10**5
is_prime = eratos(inf)
like_2007 = [0]*(inf+1)
for i in range(1, inf+1):
    if is_prime[i] == 1 and i % 2 == 1:
        if is_prime[(i+1)//2]:
            like_2007[i] = 1
cumsum = list(accumulate(like_2007))
# print(like_2007)
# print(cumsum)

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 is_prime

def main():
    q=int(input())
    is_prime = primes(10**5+1)
    a = [0 for i in range(10**5+1)]
    for i in range(3,10**5+1):
        if is_prime[i] and is_prime[(i+1)//2]:a[i]+=1
    for i in range(3,10**5+1):a[i]+=a[i-1]
    for i in range(q):
        l,r=map(int,input().split())
        print(a[r]-a[l-1])

main()

Submission status: Accepted

Solution code:
def erat(M):
    p = [1] * M
    p[0] = p[1] = 0
    for x in range(2, int((M - 1)**.5) + 1):
        if p[x]:
            for y in range(x*x, M, x):
                p[y] = 0
    return p
INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
from itertools import*
for i in range(INF):
    q[i] = i%2 * p[i] * p[-~i//2]
*a, = accumulate([0] + q)
for _ in [None] * int(input()):
    l, r = map(int, input().split())
    print(a[-~r] - a[l])

Submission status: Accepted

Solution code:
a=[0 for i in range(10**5+3)]
b=[1 for i in range(10**5+3)]
for i in range(2,10**5+3):
    if b[i]==1:
        for j in range(2*i,10**5+3,i):
            b[j]=0
b[0]=0
b[1]=0
for i in range(1,10**5+3,2):
    a[i]=b[i] and b[(i+1)//2]
e=[a[0]]
for i in range(1,10**5+3):
    e.append(a[i]+e[i-1])
#print(e)
for i in range(int(input())):
    l,r=map(int,input().split())
    print(e[r]-e[l-1])

Submission status: Accepted

Solution code:
# AtCoder ABC84 D -2017-like NUmber
# 累積和とエラトステネスのふるいを使用

Q = int(input())

# 十分な値の範囲を取っておく
MAX = 101010
A   = [1]*MAX

# 0と1は素数から除外
A[0] = 0
A[1] = 0

# エラトステネスのふるい
# 素数以外の値をふるい落とす
for n in range(2, MAX):
    i = n * 2
    while i < MAX:
        A[i] = 0
        i += n

# 2017に似た数を0から1にする
a = [0]*MAX
for n in range(MAX):
    if n % 2 == 0:
        continue
    if A[n] and A[(n+1)//2]:
        a[n] = 1

# 累積和
S = [0]*(MAX+1)
for n in range(MAX):
    S[n+1] = S[n] + a[n]

# l, rの範囲の総和を求める
B = []
for q in range(Q):
    l, r = map(int, input().split())
    r += 1
    B.append(S[r] - S[l-1])

for b in B:
    print(b)

Submission status: Accepted

Solution code:
def primes(n):#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]], is_prime
li_p, is_prime = primes(10**5+1)
li_p.reverse()
for i in li_p:
    if  is_prime[int((i+1)/2)]:
        continue
    else:
        is_prime[i] = False
res = [0] * (10**5+1)
for i in range(10**5+1):
    if i == 0:
        continue
    if is_prime[i]:
        res[i] = res[i-1] + 1
    else:
        res[i] = res[i-1]
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    if l>0:
        print(res[r] - res[l-1])
    else:
        print(res[r])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Q = int(input())

MAX = 10 ** 5 + 2

is_prime = [True] * MAX

is_prime[0] = False
is_prime[1] = False
i = 2
while i ** 2 <= MAX:
    if is_prime[i]:
        for j in range(i * 2, MAX, i):
            is_prime[j] = False
    i += 1

count = [0] * MAX
for i in range(2, MAX):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        count[i] = 1
ans = [0] * MAX
for i in range(1, MAX):
    ans[i] = ans[i - 1] + count[i - 1]

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

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)
max_r = max(r)

is_sosu = [1] * (max_r + 1)
is_sosu[0] = is_sosu[1] = 0
for i in range(2, max_r+1):
    if is_sosu[i]:
        for j in range(i*i, max_r+1, i):
            is_sosu[j] = 0

sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if is_sosu[i] and is_sosu[(i+1)//2]:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

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

Submission status: Accepted

Solution code:
import bisect
N = 10**5
Q = int(input())
 
lst1 = set([2])
for L in range(3, N, 2):
    if all(L % L2 != 0 for L2 in lst1):
        lst1.add(L)

lst2 = [i for i in lst1 if (i+1)//2 in lst1]
 
lst2.sort()
 
for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)

Submission status: Accepted

Solution code:
def create_prime_list(limit):
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes
    
Q = int(input())

p = set(create_prime_list(10**5))

#今注目してる数より左に出てきた「2017に似た数」
n_of_p = [0]*(10**5+2)

for i in range(1,10**5+1):
    if i%2 == 1:
        if i in p and (i+1)//2 in p:
            n_of_p[i+1] = n_of_p[i] + 1
        else:
            n_of_p[i+1] = n_of_p[i]
    else:
        n_of_p[i+1] = n_of_p[i]
        
#print(n_of_p[0:20])

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

Submission status: Accepted

Solution code:
from math import floor,sqrt

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

    for i in range(2, floor(sqrt(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
  
s = set(eratosthenes(10**5))
l = [0]*(10**5 + 1)
count = 0

for i in s:
  l[i] = 1

count = 0   
L = [0]*(10**5 + 1)

for i in range(1,10**5 + 1):
  if i != 2 and l[i] == 1 and l[(i+1)//2] == 1:
    count += 1
    L[i] = count
  else:
    L[i] = count
    

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d

import sys
input=sys.stdin.readline
            
def main():
    sv=[1]*(10**5+1)
    sv[0]=0
    sv[1]=0
    for i in range(int(10**5)+1):
        if sv[i]==0:
            continue
        k=2
        while(k*i<=10**5):
            sv[k*i]=0
            k+=1

    Q=int(input())
    LRs=[tuple(map(int,input().split())) for i in range(Q)]
    like17=[]
    for i in range(1,10**5+1,2):
        if sv[i]!=0 and sv[int((i+1)//2)]!=0:
            like17+=[i]
            
    imo=[0]*(10**5+1)
    for i in range(len(like17)):
        imo[like17[i]+1]=1
    for i in range(10**5):
        imo[i+1]+=imo[i]
    
    for lr in LRs:
        l=lr[0]
        r=lr[1]
        print(imo[r+1]-imo[l])
        
    
if __name__=="__main__":
    main()

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())
l=[]
r=[]
for i in range(q):
    ll,rr=map(int,input().split())
    l.append(ll)
    r.append(rr)

similar=[]
cnt=0
for i in range(10**5+2):
    if i<=2:
        similar.append(0)
    else:
        if is_prime(i)==True and (is_prime((i+1)/2))==True:
            cnt+=1
        similar.append(cnt)

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate


def main():
    input = stdin.buffer.readline
    MAX = 10 ** 5
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]

    dp = [1] * (MAX + 1)
    dp[0] = dp[1] = 0
    for i in range(2, MAX + 1):
        if dp[i]:
            x = 2
            while i * x < MAX + 1:
                dp[i * x] = 0
                x += 1
    for i in reversed(range(2, MAX + 1)):
        if not dp[(i + 1) // 2]:
            dp[i] = 0

    summary = list(accumulate(dp))

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

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

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

from itertools import accumulate
acc=list(accumulate(prime_list))

for lr_i in lr:
    print(acc[lr_i[1]]-acc[lr_i[0]-1])

Submission status: Accepted

Solution code:
q = int(input())
prime = [True for _ in range(10 ** 5 + 1)]
prime[0] = False
prime[1] = False
ans = [0 for _ in range(10 ** 5 + 1)]
total = 0
for num in range(2, 10 ** 5 + 1):
    if prime[num]:
        tmp = num * 2
        while tmp <= 10 ** 5:
            prime[tmp] = False
            tmp += num
        if prime[(num + 1) // 2]:
            total += 1
    ans[num] = total
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])

Submission status: Accepted

Solution code:
import math

Q = int(input())

def prime(n):
	if n > 1:
		for i in range(2,math.floor(math.sqrt(n))+1):
			if (n % i) == 0:
				return(False)
				break
		else:
			return(True)
	else:
		return(False)

Numero = [0]*100001
for i in range (1, 50001):
	if prime(2*i+1) == 1 and prime(i+1) == 1:
		for j in range (2*i+1, 100001):
			Numero[j]+=1
	else:
		continue

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

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

table = primes(10**5+10)
# print(table)
set_table = set(table)

kisuu = [v for v in table if (v+1)//2 in set_table]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(bisect_right(kisuu, r) - bisect_left(kisuu, l))

Submission status: Accepted

Solution code:
q = int (input())

def pr(n):
    L = [1]*(n+1)
    L[0] = 0
    L[1] = 0
    for i in range(2,n+1):
        for j in range(2*i,n,i):
            L[j] = 0
    return L
    
a = pr(100001)

li = [0]*(100001)
for i in range(1,100000,2):
    if a[i] and a[(i+1)//2]:
        li[i] = 1
        
from itertools import accumulate
b = list(accumulate(li))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate
def erat(m):
    p = [1] * m
    p[0] = p[1] = 0
    for x in range(2, int((~-m)**.5) + 1):
        if p[x]:
            for y in range(x*x, m, x):
                p[y] = 0
    return p

INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
for n in range(INF):
    q[n] = n%2 * p[n] * p[-~n//2]
*a, = accumulate([0] + q)
for _ in [None] * int(input()):
    l, r = map(int, input().split())
    print(a[r + 1] - a[l])

Submission status: Accepted

Solution code:
#ABC084D
def main():
    import sys
    Q = int(sys.stdin.readline())
    LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    #print(LR)
    
    check = [1 for _ in range(10**5+1)]
    check[0], check[1] = 0, 0
    for i in range(2, 10**5+1):
        if check[i] ==0:
            continue
        elif check[i] ==1:
            for j in range(2*i, 10**5+1, i):
                check[j] =0
    check2 = check.copy()
    for i in range(2, 10**5+1):
        if check[i]==1:
            #print((i+1)/2, check[(i+1)//2])
            if (i+1)%2==0 and check[(i+1)//2] ==1:
                continue
            else:
                check2[i] = 0
    
    #累積和
    for i in range(1, 10**5+1):
        check2[i] = check2[i-1] + check2[i]
    #print(check2)
    for lr in LR:
        print(check2[lr[1]] - check2[lr[0]-1])
                


if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt
from itertools import accumulate

L = [0 for _ in range(10**5)]
check = [1 for _ in range(10**5)]
check[0],check[1] = 0,0
for i in range(2,10**5):
  if check[i]:
    for j in range(i**2,10**5,i):
      check[j] = 0

for i in range(3,10**5,2):
  if check[i] == 1 and check[((i+1)//2)] == 1:
    L[i] = 1

Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
ans = list(accumulate(L))
for l,r in lr:
  print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import numpy as np
from math import sqrt
from itertools import accumulate

L = [0 for _ in range(10**5)]
check = [1 for _ in range(10**5)]
check[0],check[1] = 0,0
for i in range(2,10**5):
  if check[i]:
    for j in range(i**2,10**5,i):
      check[j] = 0

for i in range(3,10**5,2):
  if check[i] == 1 and check[((i+1)//2)] == 1:
    L[i] = 1

Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
ans = list(accumulate(L))
for l,r in lr:
  print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
N=10**5
prime=[1]*(N+1)
prime[0]=prime[1]=0
for i in range(2,int(N**.5)+1):
    if not prime[i]:
        continue
    for j in range(i*2,N+1,i):
        prime[j]=0

check=[0]*(N+1)
for n in range(N+1):
    if n%2==1 and prime[n] and prime[(n+1)//2]:
        check[n]=1

accumulate=[0]*(N+1)
for n in range(1,N+1):
    accumulate[n]=accumulate[n-1]+check[n]

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

Submission status: Accepted

Solution code:
import sys
import math

#必要な素数を全列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return set(P)

max_n = 10**5

primes = eratosthenes(max_n)
# print(primes)

a = [0] * (max_n+1)
for i in range(1, max_n + 1):
    if i in primes and (i+1)//2 in primes:
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
# print(a)

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

Submission status: Accepted

Solution code:
import sys

Q = int(sys.stdin.readline().strip())
LR = []
for i in range(Q):
    LR.append([int(x) for x in sys.stdin.readline().strip().split()])

N = 10**5+1
Primes = list(range(N+1))
Primes[1] = 0

for p in Primes:
    if p * p > N+1: break
    if p == 0: continue
    for i in range(p + p, N+1, p):
        Primes[i] = 0

primes = [p for p in Primes if p > 0]

likes = []
r = 0
for n in range(N):
    if n%2 == 1 and Primes[n] > 0 and Primes[n//2+1] > 0:
        r += 1
    likes.append(r)

for i in range(Q):
    print(likes[LR[i][1]] - likes[LR[i][0]-1])

Submission status: Accepted

Solution code:
import numpy as np
q = int(input())
b = [True] * (10**5+1)
for i in range(2, 10**5):
    if not b[i]:
        continue
    x = 2 * i
    while x <= 10**5:
        b[x] = False
        x += i
b[0] = b[1] = False
a = [False] *  (10**5+1)
for i in range(1, 10**5, 2):
    if b[i] and b[int((i+1)/2)]:
        a[i] = True
cumsum = np.array(a).cumsum()
for _ in range(q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l-1])

Submission status: Accepted

Solution code:
import numpy as np
q = int(input())
b = [True] * (10**5+1)
for i in range(2, 10**5):
    if not b[i]:
        continue
    x = 2 * i
    while x <= 10**5:
        b[x] = False
        x += i
b[0] = b[1] = False
a = [False] *  (10**5+1)
for i in range(1, 10**5):
    if b[i] and b[int((i+1)/2)]:
        a[i] = True
cumsum = np.array(a).cumsum()
for _ in range(q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l-1])

Submission status: Accepted

Solution code:
import numpy as np
q = int(input())
b = [True] * (10**5+1)
for i in range(2, 10**5):
    x = 2 * i
    while x <= 10**5:
        b[x] = False
        x += i
b[0] = b[1] = False
a = [False] *  (10**5+1)
for i in range(1, 10**5):
    if b[i] and b[int((i+1)/2)]:
        a[i] = True
cumsum = np.array(a).cumsum()
for _ in range(q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l-1])

Submission status: Accepted

Solution code:
import itertools
n=int(input())
d=[list(map(int,input().split())) for i in range(n)]

sosuu=[1 for i in range(10**5+1)]
#sosuuのindexの値が1の時素数とする。
sosuu[0]=0
sosuu[1]=0
for i in range(2,10**5+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1:
    for j in range(2*i,10**5+1,i):
      sosuu[j]=0
like_n=[]
like_n+=sosuu
#奇数なので、2を削除。
like_n[2]=0
for i in range(3,10**5+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1 and sosuu[(i+1)//2]==0:
    like_n[i]=0
ans= list(itertools.accumulate(like_n))
for ans_d in d:
  print(ans[ans_d[1]]-ans[ans_d[0]-1])

Submission status: Accepted

Solution code:
import itertools

isPrime = [True]*(10**5+1)
similar = [0]*(10**5+1)
isPrime[0] = False
isPrime[1] = False
def sieve(n):
    for i in range(2, n+1):
        if isPrime[i]:
            if isPrime[(i+1)//2]:
                similar[i] = 1
            for j in range(i*2, n+1, i):
                isPrime[j] = False

sieve(10**5)

acm = list(itertools.accumulate(similar))

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

Submission status: Accepted

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

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

like_2017 = [is_prime(n) and is_prime((n+1)//2) for n in range(1, 100001, 2)]
cumsum = [0] * len(like_2017)
cumsum[0] = like_2017[0]
for i in range(1, len(cumsum)):
    cumsum[i] = cumsum[i-1] + like_2017[i]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    l, r = l // 2, r // 2
    if l == 0:
        print(cumsum[r])
    else:
        print(cumsum[r] - cumsum[l-1])

Submission status: Accepted

Solution code:
q = int(input())

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

def primes(n):
    # 1であれば素数であるリスト
    primes = [1] * (n+1)
    primes[0] = 0
    primes[1] = 0

    for i in range(2, int(n**0.5) + 1):
        if not primes[i]:
            continue
        for j in range(i * 2, n + 1, i):
            primes[j] = 0
    return primes

MAX = 100000
prime_list = primes(MAX)

# 2017に似た数値かどうかを求めるための累積和用のリスト作成
ans_list = [0] * (MAX + 1)
now = 0
for i in range(MAX):
    if prime_list[i] == 1 and prime_list[(i+1)//2] == 1:
        now += 1
    ans_list[i+1] = now

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

Submission status: Accepted

Solution code:
import math
import itertools
import sys

prime_numbers = set()
table = [0 for i in range(10 ** 5 + 1)]
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def is_like_2017(x):
    return is_primenumber(x) and is_primenumber((x + 1) // 2)


def query(l, r):
    print(table[r] - table[l - 1])


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1, 2):
        if is_like_2017(i):
            table[i] += 1
    table = [x for x in itertools.accumulate(table)]
    Q = int(input())

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)

Submission status: Accepted

Solution code:
import math
import bisect
import sys
input = sys.stdin.readline
q = int(input())

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

prime = set([i for i, f in enumerate(sieve_of_erastosthenes(10**5)) if f])
like = []
for p in prime:
    if (p+1)//2 in prime:
        like.append(p)
like.sort()

for i in range(q):
    l, r = map(int, input().split())
    st = bisect.bisect_left(like, l)
    en = bisect.bisect_right(like, r)

    print(en-st)

Submission status: Accepted

Solution code:
p = [2, 3]
for i in range(5, 10 ** 5 + 1, 2):
  flag = True
  j = 0
  while p[j] * p[j] <= i:
    if i % p[j] == 0:
      flag = False
      break
    j += 1
  if flag:
    p.append(i)

tf = [False] * (10 ** 5 + 1)
for i in p:
  tf[i] = True

like = [0]
for i in range(1, 10 ** 5 + 1):
  if tf[i] and tf[(i + 1) // 2]:
    like.append(like[-1] + 1)
  else:
    like.append(like[-1])

ans = []
q = int(input())
for _ in range(q):
  i, j = map(int, input().split())
  i -= 1
  ans.append(like[j] - like[i])

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
# 下記ページを参考に実装している
# https://qiita.com/drken/items/56a6b68edef8fc605821#%E5%95%8F%E9%A1%8C-2-atcoder-abc-084-d---2017-like-number

# エラトステネスのふるいで最大値までの素数をO(1)で判別できるようにする

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

# 2017と似た数字かどうか
like2017 = [0] * MAX
for i in range(2, MAX):
  if is_prime[i] and is_prime[(i+1)//2]:
    like2017[i] = 1

# 累積和
s = [0] * (MAX+1)
for i in range(MAX):
  s[i+1] = s[i] + like2017[i]
#print(is_prime[:10])
#print(like2017[:10])
#print(s[:10])

# クエリ処理
q = int(input())
for i in range(q):
  l, r = map(int, input().split())
  print(s[r+1] - s[l])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
from math import sqrt

def main():
    input = stdin.readline

    h = defaultdict(int)
    h[2] = 1
    for i in range(3, 100000, 2):
        for j in range(3, int(sqrt(i)) + 1, 2):
            while i % j == 0:
                h[j] = 1
                i //= j
        if i > 1:
            h[i] = 1
    k = [0] * 100001
    for key in h.keys():
        if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
            k[key] = 1
    for i in range(1, 100001):
        k[i] += k[i - 1]
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        print(k[r] - k[l - 1])
main()