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:
l=[3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061, 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273, 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413, 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361, 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477, 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521, 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661, 9721, 9817, 9901, 9973, 10333, 10357, 10453, 10837, 10861, 10957, 11113, 11161, 11317, 11497, 11677, 11701, 12073, 12157, 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721, 12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933, 14437, 14593, 
14737, 14821, 15013, 15073, 15121, 15241, 15277, 15361, 15373, 15733, 15901, 16033, 16333, 16381, 16417, 16573, 16633, 16657, 16921, 17041, 17053, 17077, 17257, 17293, 17377, 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301, 18313, 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717, 19801, 19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061, 21193, 21277, 21313, 21577, 21661, 21673, 21817, 22093, 22501, 22573, 22621, 22993, 23053, 23173, 23557, 23677, 23773, 23917, 24097, 24421, 24481, 24781, 24841, 25033, 25153, 25237, 25561, 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833, 26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 
28057, 28297, 28393, 28813, 28837, 28921, 29101, 29473, 29641, 30181, 30241, 30517, 30553, 30577, 30637, 30661, 30697, 30781, 30853, 31081, 31237, 31321, 31333, 31357, 31477, 31573, 31873, 31981, 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457, 33493, 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981, 35317, 35521, 35677, 35977, 36097, 36241, 36433, 36457, 36793, 36877, 36901, 36913, 37273, 37321, 37357, 37573, 37717, 37957, 38281, 38461, 38833, 38953, 38977, 39217, 39373, 39397, 39733, 40093, 40177, 40213, 40693, 40813, 41017, 41221, 41281, 41413, 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177, 43201, 43321, 43573, 43597, 43633, 
43717, 44053, 44101, 44221, 44257, 44293, 44893, 45061, 45337, 45433, 45481, 45553, 45613, 45841, 46021, 46141, 46261, 46861, 46993, 47017, 47161, 47353, 47521, 47533, 47653, 47713, 47737, 47797, 47857, 48121, 48193, 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417, 49597, 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217, 51241, 51481, 51517, 51637, 52057, 52081, 52237, 52321, 52453, 52501, 52813, 52861, 52957, 53077, 53113, 53281, 53401, 53917, 54121, 54133, 54181, 54217, 54421, 54517, 54541, 54673, 54721, 54973, 55057, 55381, 55501, 55633, 55837, 55921, 55933, 56053, 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857, 56893, 57073, 
57097, 57193, 57241, 57373, 57457, 57853, 58153, 58417, 58441, 58537, 58573, 58693, 59053, 59197, 59221, 59281, 59341, 59833, 60217, 60337, 60373, 60637, 60733, 60937, 61057, 61153, 61261, 61297, 61561, 61657, 61681, 61717, 61861, 62137, 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541, 63697, 63781, 63913, 64153, 64237, 64381, 64513, 64717, 65173, 65293, 65413, 65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601, 66697, 66853, 66973, 67057, 67153, 67273, 67477, 67537, 67741, 67777, 67933, 67993, 68113, 68281, 68521, 68737, 69001, 69073, 69457, 69493, 69697, 69877, 70117, 70177, 70297, 70501, 70621, 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 
72481, 72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077, 74317, 74377, 74713, 75013, 75133, 75181, 75721, 75793, 75913, 76333, 76561, 76597, 76753, 77137, 77641, 78157, 78193, 78277, 78877, 78901, 79333, 79357, 79537, 79657, 79693, 79801, 79873, 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013, 81181, 81517, 81637, 81853, 82021, 82153, 82261, 82561, 82981, 83077, 83221, 83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673, 84697, 84793, 84913, 85297, 85333, 85453, 85717, 85933, 86353, 86413, 87181, 87253, 87337, 87421, 87433, 87517, 87553, 87973, 88117, 88177, 88237, 88261, 88513, 88741, 88897, 88993, 89293, 89833, 89917, 90121, 91081, 91381, 
91393, 91513, 91957, 92041, 92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637, 93913, 94033, 94117, 94273, 94321, 94441, 94573, 94777, 94837, 94993, 95257, 95317, 95401, 95581, 95617, 95713, 95737, 96097, 96157, 96181, 96493, 96517, 96973, 97081, 97177, 97501, 97561, 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661, 99877]
from bisect import bisect_left as bl,bisect_right as br
q=int(input())
for i in range(q):
    le,r=map(int,input().split())
    print(br(l,r)-bl(l,le))

Submission status: Accepted

Solution code:
import numpy as np

q = int(input())

# 素数列挙
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)

arr = np.array(list(primes))
arr = np.bincount(arr)

# 素数かつ2017に似た数を列挙
like_2017 = np.zeros(n, bool)
for i in np.where(arr == 1)[0]:
    if (i + 1) // 2 in primes:
        like_2017[i] = True

like_2017 = like_2017.cumsum()


def cnt_primes(l, r):
    return like_2017[r] - like_2017[l - 1]


ans = []
for _ in range(q):
    tmp = 0
    l, r = map(int, input().split())
    tmp += cnt_primes(l, r)
    ans.append(tmp)

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
q = int(input())
lis=[]
maxr=0
minl=float('inf')
for i in range(q):
    l,r = map(int, input().split())
    maxr=max(maxr,r)
    minl=min(minl,int((l+1)/2))
    lis.append((l,r))
primes=[0]*(maxr+1)
if maxr>=2:
    primes[2]=1
for i in range(minl, maxr+1):
    if i%2==0:
        continue
    is_prime=True
    maxcheck=int(i**0.5+1)
    for j in range(3,maxcheck+1):
        if i%j==0:
            is_prime=False
            break
    if is_prime:
        primes[i]=1
like2017=[0]*(maxr+1)
#print(primes)
for i in range(3,maxr+1):
    if primes[i]==1 and primes[int((i+1)/2)]==1:
        like2017[i]=1
    like2017[i]+=like2017[i-1]
#print(like2017)
for l,r in lis:
    print(like2017[r]-like2017[l-1])

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(N):
    prime_list = [True] * (N + 1)
    prime_list[0] = prime_list[1] = False
    ans_list = [0] * (N + 1)
    for i in range(2, N+1):
        if prime_list[i]:
            for j in range(i*2, N+1, i):
                prime_list[j] = False
    for i in range(1, N+1):
        ans_list[i] = ans_list[i - 1]
        if i % 2 != 0:
            j = (i + 1) // 2
            if prime_list[i] and prime_list[j]:
                ans_list[i] += 1
    return ans_list

def main():
    ans_list = sieve_of_eratosthenes(10 ** 5)
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(ans_list[r] - ans_list[l - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from collections import deque
from collections import defaultdict

import bisect

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	#data = [2]
	data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	#ans = [x for x in data if x!=0]
	ans = data[:]
	return ans

q = readInt()
lr = []

maxNumber = 100000

for i in range(q):
	lr.append(readInts())


pri = get_sieve_of_eratosthenes(maxNumber)
simi = [0 for i in range(maxNumber+1)]
simi[3] = 1
for i in range(4,len(pri)):
	x = pri[i]
	if x!=0 and pri[(x+1)//2]!=0:
		simi[i] = simi[i-1]+1
	else:
		simi[i] = simi[i-1]

#print(simi[:10])

for item in lr:
	print(simi[item[1]]-simi[item[0]-1])

Submission status: Accepted

Solution code:
import math
from collections import deque
from collections import defaultdict

import bisect

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	return ans

q = readInt()
lr = []

maxNumber = 100000

for i in range(q):
	lr.append(readInts())


pri = get_sieve_of_eratosthenes(maxNumber)
simi = []

for i in range(1,len(pri)):
	if pri[bisect.bisect_left(pri,(pri[i]+1)//2)]==(pri[i]+1)//2:
		simi.append(pri[i])

for item in lr:
	print(len(simi[bisect.bisect_left(simi,item[0]):bisect.bisect_right(simi,item[1])]))

Submission status: Accepted

Solution code:
def l(): return list(map(int, input().split()))
def m(): return map(int, input().split())

def sieve(n): # エラトステネスの篩ですよ
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return num

def main():
  q = int(input())
  l , r = [0]*q, [0]*q
  for i in range(q):
    l[i], r[i] = m()
  rr = 101010
  prime = sieve(rr+1)
  # print(prime)
  likp = [0]*rr
  for i in range(rr):
    if i % 2 == 0: continue
    if prime[i] and prime[(i+2)//2]: likp[i] = 1
  # print(likp)
  sm = [0]*(rr+1)
  for i in range(rr):
    sm[i+1] = sm[i] + likp[i]
  # print(sm)
  for i in range(q):
    print(sm[r[i]+1] - sm[l[i]])

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def l(): return list(map(int, input().split()))
def m(): return map(int, input().split())

def sieve(n): # エラトステネスの篩ですよ
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

def main():
  q = int(input())
  l , r = [0]*q, [0]*q
  for i in range(q):
    l[i], r[i] = m()
  rr = max(r) 
  prime = sieve(rr+1)
  # print(prime)
  likp = [0]*rr
  for i in prime:
    if (i+1) // 2 in prime:
      likp[i-1] = 1
  # print(likp)
  sm = [0]*(rr+1)
  for i in range(rr):
    sm[i+1] = sm[i] + likp[i]
  # print(sm)
  for i in range(q):
    print(sm[r[i]] - sm[l[i]-1])

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def l(): return list(map(int, input().split()))
def m(): return map(int, input().split())

def sieve(n): # エラトステネスの篩ですよ
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

def main():
  q = int(input())
  l , r = [0]*q, [0]*q
  for i in range(q):
    l[i], r[i] = m()
  rr = max(r) 
  prime = sieve(rr+1)
  # print(prime)
  likp = [0]*rr
  for i in prime:
    if (i+1) // 2 in prime:
      likp[i-1] = 1
  # print(likp)
  sm = [0]*(rr+1)
  for i in range(rr):
    sm[i+1] = sm[i] + likp[i]
  # print(sm)
  for i in range(q):
    print(sm[r[i]] - sm[l[i]-1])
   


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

def get_sieve_of_eratosthenes(n):
  prime = []
  limit = math.sqrt(n)
  data  = list(range(2, n+1))
  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_value = 10**5

is_prime = defaultdict(bool)

prime_list = get_sieve_of_eratosthenes(max_value)

for i in prime_list:
  is_prime[i] = True
  
a = [0]*(max_value)
for i in range(3, max_value, 2):
  if is_prime[i]& is_prime[int((i+1)/2)]:
    a[i] = 1

b = [0]*(max_value+1)
for i in range(max_value):
  b[i+1] = b[i] + a[i]

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

Submission status: Accepted

Solution code:
import math


def sushu(n):
    arr = []
    for i in range(2, n + 1):
        arr.append(i)

    limit = int(math.sqrt(n)) + 1

    prev = []
    while True:
        start = arr[0]
        prev.append(start)
        if start > limit:
            break
        brr = []
        for i in arr:
            if i % start != 0:
                brr.append(i)
        arr = brr

    prev.extend(arr)
    return prev


n = 100000
shushu = sushu(100000)

marks = []
for i in range(n + 1):
    marks.append(False)

for j in shushu:
    marks[j] = True

marks2 = []
result = []
for i in range(n + 1):
    if i % 2 == 0:
        marks2.append(False)
        if i == 0:
            result.append(0)
        else:
            result.append(result[i - 1])
    else:
        if marks[(i + 1) // 2] and marks[i]:
            marks2.append(True)
            result.append(result[i - 1] + 1)
        else:
            marks2.append(False)
            result.append(result[i - 1])

Q = 4
ARR = [
    [13, 13],
    [7, 11],
    [7, 11],
    [2017, 2017]
]

Q = 6
ARR = [
    [1, 53],
    [13, 91],
    [37, 55],
    [19, 51],
    [73, 91],
    [13, 49]
]

Q = int(input())

ARR = []

for i in range(Q):
    ARR.append(list(map(int, input().split())))

for i in range(Q):
    start = ARR[i][0]
    end = ARR[i][1]
    print(result[end] - result[start - 1])

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


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

primes = set(get_sieve_of_eratosthenes(10**5))
like2017s = []
cnt_dict = {}
cnt_dict[-1] = 0
for i in range(10**5//2):
    num = i*2+1
    num2 = (num+1)//2
    if num in primes and num2 in primes:
        cnt_dict[num] = cnt_dict[num-2]+1
    else:
        cnt_dict[num] = cnt_dict[num-2]

for lr in lrl:
    l,r = lr
    print(cnt_dict[r]-cnt_dict[l-2])

Submission status: Accepted

Solution code:
Q = int(input())

prime = [True] * 100001
prime[0] = False
prime[1] = False

for i in range(2, 50001):
  if not prime[i]:
    continue
  now = i
  while now+i <= 100000:
    now += i
    prime[now] = False
    
ans = [0] * (100001)
for i in range(1, 100001):
  if i%2 == 0:
    ans[i] = ans[i-1]
  else:
    if prime[i] and prime[(i+1)//2]:
      ans[i] = ans[i-1] + 1
    else:
      ans[i] = ans[i-1]
      
for i in range(Q):
  l, r = map(int, input().split())
  print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import bisect
like = [3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061, 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273, 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413, 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361, 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477, 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521, 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661, 9721, 9817, 9901, 9973, 10333, 10357, 10453, 10837, 10861, 10957, 11113, 11161, 11317, 11497, 11677, 11701, 12073, 12157, 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721, 12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933, 14437, 14593, 14737, 14821, 15013, 15073, 15121, 15241, 15277, 15361, 15373, 15733, 15901, 16033, 16333, 16381, 16417, 16573, 16633, 16657, 16921, 17041, 17053, 17077, 17257, 17293, 17377, 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301, 18313, 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717, 19801, 19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061, 21193, 21277, 21313, 21577, 21661, 21673, 21817, 22093, 22501, 22573, 22621, 22993, 23053, 23173, 23557, 23677, 23773, 23917, 24097, 24421, 24481, 24781, 24841, 25033, 25153, 25237, 25561, 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833, 26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 28057, 28297, 28393, 28813, 28837, 28921, 29101, 29473, 29641, 30181, 30241, 30517, 30553, 30577, 30637, 30661, 30697, 30781, 30853, 31081, 31237, 31321, 31333, 31357, 31477, 31573, 31873, 31981, 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457, 33493, 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981, 35317, 35521, 35677, 35977, 36097, 36241, 36433, 36457, 36793, 36877, 36901, 36913, 37273, 37321, 37357, 37573, 37717, 37957, 38281, 38461, 38833, 38953, 38977, 39217, 39373, 39397, 39733, 40093, 40177, 40213, 40693, 40813, 41017, 41221, 41281, 41413, 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177, 43201, 43321, 43573, 43597, 43633, 43717, 44053, 44101, 44221, 44257, 44293, 44893, 45061, 45337, 45433, 45481, 45553, 45613, 45841, 46021, 46141, 46261, 46861, 46993, 47017, 47161, 47353, 47521, 47533, 47653, 47713, 47737, 47797, 47857, 48121, 48193, 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417, 49597, 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217, 51241, 51481, 51517, 51637, 52057, 52081, 52237, 52321, 52453, 52501, 52813, 52861, 52957, 53077, 53113, 53281, 53401, 53917, 54121, 54133, 54181, 54217, 54421, 54517, 54541, 54673, 54721, 54973, 55057, 55381, 55501, 55633, 55837, 55921, 55933, 56053, 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857, 56893, 57073, 57097, 57193, 57241, 57373, 57457, 57853, 58153, 58417, 58441, 58537, 58573, 58693, 59053, 59197, 59221, 59281, 59341, 59833, 60217, 60337, 60373, 60637, 60733, 60937, 61057, 61153, 61261, 61297, 61561, 61657, 61681, 61717, 61861, 62137, 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541, 63697, 63781, 63913, 64153, 64237, 64381, 64513, 64717, 65173, 65293, 65413, 65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601, 66697, 66853, 66973, 67057, 67153, 67273, 67477, 67537, 67741, 67777, 67933, 67993, 68113, 68281, 68521, 68737, 69001, 69073, 69457, 69493, 69697, 69877, 70117, 70177, 70297, 70501, 70621, 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 72481, 72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077, 74317, 74377, 74713, 75013, 75133, 75181, 75721, 75793, 75913, 76333, 76561, 76597, 76753, 77137, 77641, 78157, 78193, 78277, 78877, 78901, 79333, 79357, 79537, 79657, 79693, 79801, 79873, 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013, 81181, 81517, 81637, 81853, 82021, 82153, 82261, 82561, 82981, 83077, 83221, 83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673, 84697, 84793, 84913, 85297, 85333, 85453, 85717, 85933, 86353, 86413, 87181, 87253, 87337, 87421, 87433, 87517, 87553, 87973, 88117, 88177, 88237, 88261, 88513, 88741, 88897, 88993, 89293, 89833, 89917, 90121, 91081, 91381, 91393, 91513, 91957, 92041, 92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637, 93913, 94033, 94117, 94273, 94321, 94441, 94573, 94777, 94837, 94993, 95257, 95317, 95401, 95581, 95617, 95713, 95737, 96097, 96157, 96181, 96493, 96517, 96973, 97081, 97177, 97501, 97561, 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661, 99877]
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(bisect.bisect_right(like,r)-bisect.bisect_left(like,l))

Submission status: Accepted

Solution code:
import math

Q = int(input())
sosu = [2]

for L in range(3, 10**5, 2): # 2 以外の素数は奇数なので
    for L2 in sosu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosu.append(L)

sosu = set(sosu)

d = {0:0}
now = 0
for x in range(1, 10**5+1):
    if x % 2 == 1:
        if x in sosu and (x+1)/2 in sosu:
            now += 1
    d[x] = now

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

for l,r in li:
    ans = 0
    print(d[r]-d[l-1])

Submission status: Accepted

Solution code:
def main():
    Q = int(input())
    LENGTH = 1 + 10**5

    primes = [True] * LENGTH 
    primes[0] = False
    primes[1] = False
    for i in range(2, int(LENGTH ** 0.5 + 1)):
        if primes[i] == False:
            continue
        for j in range(i*2, LENGTH, i):
            primes[j] = False

    sol = [0] * LENGTH

    cnt = 0
    for i in range(3,len(sol)):
        if not primes[i]:
            sol[i] = cnt
            continue
        cnt += 1 if primes[i] and primes[(i+1)//2] else 0
        sol[i] = cnt

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

if __name__ == "__main__":
    main()

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)
    
    def calc(N):
        import math
        for i in range(3, int(math.sqrt(N))+1):
            while N % i==0:
                N =N//i
                return 0
        else:
            num = (N+1)//2
            #if num ==2:
                #return N
            for j in range(2, int(math.sqrt(num)+1)):
                while num % j==0:
                    num = num//j
                    return 0
            else:
                return N
    
     
    L = []
    for i in range(3, 10**5+1, 2):
        tmp = calc(i)
        if tmp !=0:
            L+=[tmp]
    #print(L)
    import bisect
    
    for row in LR:
        l = bisect.bisect_left(L, row[0])
        r = bisect.bisect_right(L, row[1])
        print(r-l)

if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
10**5以下の各数に対して、その数字以下の2017に似た数の個数をカウントしておく。
"""
prime = [1]*(10**5+1)
prime[0] = 0
prime[1] = 1
count = [0,0]
for i in range(2,10**5+1):
    count.append(count[-1])
    if prime[i]:
        for j in range(i*i,10**5+1,i):
            prime[j] = 0
        if i>2 and prime[(i+1)//2]==1:
            count[-1] += 1

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

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

Q = I()
lr = [LI() for i in range(Q)]

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)),n+1):
        if A[i] == 1:
            prime_list.append(i)
    return A

prime = sieve_of_eratosthenes(10**5)
prime_like_2017 = [0]*(10**5+1)
prime_like_2017[3] = 1

for i in range(3,10**5+1):
    if prime[i] == 0:
        continue
    elif i == 2:
        continue
    elif i == 3:
        prime_like_2017[i] = 1
    elif i % 4 == 3:
        continue
    else:
        if prime[(i+1)//2] == 1:
            prime_like_2017[i] = 1

from itertools import accumulate

P = list(accumulate(prime_like_2017))  # P[i] = iまでに2017に似た数が何個あるか

for i in range(Q):
    print(P[lr[i][1]]-P[lr[i][0]-1])

Submission status: Accepted

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

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


A = [0] * 10 ** 5
B = [0] * 10 ** 5
con = 0

for i in range(10 ** 5):
  if isprime(i):
    A[i] = 1
  if A[i] and A[(i + 1) // 2]:
    con += 1
  B[i] = con

Q = int(input())

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

Submission status: Accepted

Solution code:
import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
q = ri()
lr = [rl() for _ in range(q)]

def Is_prime(n):
    if n<2:return False
    elif n==2:return True
    elif n>3 and n%2==0:return False
    for i in range(3, n):
        if i*i>n:
            break
        if n%i==0:return False
    return True

dp=[0]*(10**5+1)
for i in range(1,10**5+1):
    if i%2==0:
        dp[i]=dp[i-1]
    if Is_prime(i) and Is_prime((i+1)//2):
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]

for j in lr:
    print(dp[j[1]]-dp[j[0]-1])

Submission status: Accepted

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

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


A = [0] * 10**5
for i in range(10**5):
    if isprime(i):
        A[i] = 1

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

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

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate


def is_2017_like(num):
    if num == 1:
        return 0
    for k in range(2, int(math.sqrt(num)) + 1):
        if num % k == 0 or ((num + 1) // 2) % k == 0:
            return 0
    return 1


q = int(input())
lr = [list(map(int, input().split()))for i in range(q)]
ans = []
for i in range(1, 10 ** 5, 2):
    ans.append(is_2017_like(i))
ans = list(accumulate(ans))
for i in range(q):
    if lr[i][1] == 1:
        print(0)
    elif lr[i][1] != 1 and lr[i][0] == 1:
        print(ans[(lr[i][1] + 1) // 2 - 1] - 0)
    else:
        print(ans[(lr[i][1] + 1) // 2 - 1] - ans[(lr[i][0] + 1) // 2 - 2])