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:
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > 316: 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 P
l = eratosthenes(10**5)
ans = [0]*(10**5+1)
d = [0]*(10**5+1)
for i in l: d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[i] and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#2335

def main():
	n = 10**5+10
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))

	li=set()
	for i in primes:
		li.add(i)
		if i*2<n:
			li.add(i*2)
	li=list(li)
	li.sort()
	#print(li)

	li2=[0]*(n)
	for i in range(len(li)-1):
		if li[i]%2==1 and li[i+1]==li[i]+1:
			li2[li[i]]=1
	#print(li2)

	for i in range(n-1):
		li2[i+1]+=li2[i]
	#print(li2)

	q=II()
	for _ in range(q):
		l,r=MI()
		print(li2[r]-li2[l-1])





if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#エラトネスの篩
def Eratosthene(n):
    prime = [1]*(n+1)
    prime[0] = 0
    prime[1] = 0

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

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

prime = Eratosthene(10**5)
A     = [0]*len(prime)
for i in range(len(prime)):
    if prime[i]==1 and (i+1)%2==0 and prime[(i+1)//2]==1:
        A[i] = 1
S     = [0]*(len(prime)+1)

for i in range(len(prime)):
    S[i+1] = S[i] + A[i]

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

Submission status: Accepted

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

n = 10 ** 5
doubel_primes = np.zeros(n+1, dtype=int)
primes_flags = np.zeros(n+1, dtype=bool)
primes_flags[1] = True # Trueはprimeでない.
primes_flags[0] = True # Trueはprimeでない.
#primes_flags[2] = True # Trueはprimeでない.
primes_flags[::2] = True # Trueはprimeでない.
if Q >= 1:
    primes_flags[2] = False
def prime_check(n=100000):
    i = 3
    while i  < n:
        if not primes_flags[i]:
            if not primes_flags[i//2 + 1]:
                doubel_primes[i] = 1
            k = i * i
            while k <= n:
                primes_flags[k] = True
                k += i
        i += 2
        
prime_check(n)
prime_sum = doubel_primes.cumsum()
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(prime_sum[r] - prime_sum[l-1])

Submission status: Accepted

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

def primelist(x):
  limit=math.sqrt(x)
  
  prime=[]
  search=list(range(2,x+1))
  
  while 1:
    if search[0]>limit:
      prime+=search
      break
    else:
      head_num = search.pop(0)
      prime.append(head_num)
      #head_numの倍数を取り除く
      search = [num for num in search if num % head_num != 0]
      
  return prime 

prime=primelist(10**5+1)
judge=[0]
for i in range(1,10**5+2):
  if i % 2==0:
    judge.append(judge[i-1])
  else:
    if i in prime and (i+1)//2 in prime:
      judge.append(judge[i-1]+1)
    else:
      judge.append(judge[i-1])
      
for i in range(Q):
  l,r=map(int,input().split())
  print(judge[r]-judge[l-1])

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        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 -self.parents[self.find(x)]

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

    def members(self, x):
        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()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > 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 P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
q = int(input())
a = [0 for i in range(10 ** 5)]
for i in range(10 ** 5):
    if (i + 1) % 2 == 1 and is_prime(i + 1) and is_prime((i + 2) // 2):
        a[i] = 1
for i in range(1, 10 ** 5):
    a[i] += a[i - 1]
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    if l == 0:
        print(a[r])
    else:
        print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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]]


def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n //=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n //=f
        else:f +=2
    if n!=1:a.append(n)
    return a


P=prime(10**5)
A=[i for i in P if (i+1)//2 in P]
DP=[0]*(10**5+1)
for i in A:DP[i]=1
for i in range(1,10**5+1):
    DP[i]=DP[i-1]+DP[i]

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

Submission status: Accepted

Solution code:
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
def main():
  q=int(input())
  lr=[list(map(int,input().split())) for _ in range(q)]
  all=[lri[0] for lri in lr]
  all[q:q]=[lri[1] for lri in lr]
  all.sort()
  d={}
  c=0
  d[all[0]]=c
  for i in range(2*q-1):
    for j in range(all[i],all[i+1]):
      if is_prime(j) and is_prime((j+1)//2):
        c+=1
    d[all[i+1]]=c
  for l,r in lr:
    a=d[r]-d[l]
    a+=1 if is_prime(r) and is_prime((r+1)//2) else 0
    print(a)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
Q = int(input())
memo = [0]*(10**5+1)

def is_prime(N):
    prime = [True for _ in range(N)]
    prime[1] = False
    for i in range(2, N):
        if not prime[i]:
            continue
        j = i+i
        while j<N:
            prime[j] = False
            j += i
    return prime

prime = is_prime(10**5+1)

for i in range(1, 10**5+1):
    if prime[i] and prime[(i+1)//2]:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1]

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

Submission status: Accepted

Solution code:
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
n=10**5 + 1
prime = [True] * (n)
prime[0] = prime[1] = False
for i in range(2, int((n)**0.5) + 1):
    if prime[i]:
        for j in range(i*2, n, i):
            prime[j] = False
counter = 0
work = [0] * (n)
for i in range(2, n):
    if prime[i] and prime[(i+1)//2]:
        counter += 1
    work[i] = counter
for l, r in lr:
    print(work[r] - work[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

Q = int(input())

lenght = 10**5+100
prime = primes(lenght)
is_2017 = [0] * (lenght)
for i in range(1, lenght-1):
    if i%2==1 and prime[i] and prime[(i+1)//2]:
        is_2017[i] = is_2017[i-1] + 1
    else:
        is_2017[i] = is_2017[i-1]


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

Submission status: Accepted

Solution code:
#ABC 084 D
def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return [is_prime[i] for i in range(n + 1)]

era=primes(10**5)
like=[0]*(10**5)        #2は2017に似ていない
for i in range(3,10**5,2):
    if era[i] and era[int((i+1)/2)]:
        like[i]=1

cusum=[0]*(10**5)
for i in range(3,10**5,2):
    cusum[i]=cusum[i-2]+like[i]

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

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )

Submission status: Accepted

Solution code:
def prime_judge(n):
         for i in range(2,int(n**(1/2))+1):
                  if n % i == 0:
                           judge = False
                           break
         else:
                  judge = True
         return judge
x = 10**5
prime_similler = [0] * x
for i in range(3,x+1,2):
         if prime_judge(i) and prime_judge((i+1)//2):
                  prime_similler[i-1] = 1
ruiseki = [0]
for i in range(x):
         ruiseki.append(ruiseki[i] + prime_similler[i])
q = int(input())
for i in range(q):
         l,r = map(int,input().split())
         print(ruiseki[r] - ruiseki[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    Q=int(input())
    # n以下の素数のリストprimes
    n = 10**5
    primes = set(range(2, n + 1))

    # 合成数 x は p<=x**0.5を満たす素因子 p をもつという性質を利用
    for i in range(2, int(n ** 0.5 + 1)):
        primes.difference_update(range(i * 2, n + 1, i))
    primes = list(primes)
    A = [0] * (10 ** 5 + 1)

    for j in range(1,10**5+1,2):
        if j in primes and (j+1)//2 in primes:
            A[j]=1
        # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
    B = list(accumulate(A))


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




resolve()

Submission status: Accepted

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

def is_like_num(n):
    return is_prime(n) and is_prime((n+1)//2)

erast_list =[0]*100001
cnt = 0
for i in range(100001):
    if is_like_num(i):
        cnt+=1
    erast_list[i] = cnt
# print(erast_list[:5])
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
#    print(erast_list[R+1],erast_list[L-1])
    print(erast_list[R+1]-erast_list[L-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    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] = False
    return [i for i in range(n+1) if is_prime[i]]

def resolve():
    Q = I()
    lr = [LI() for _ in range(Q)]

    r_max = max([i[1] for i in lr])
    primes = set(sieve(r_max))

    acc = [0]*(r_max+2)
    for i in range(r_max+1):
        if i in primes and (i+1)//2 in primes:
            acc[i+1] = acc[i] + 1
        else:
            acc[i+1] = acc[i]

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math

prime = [2]
max = 10 ** 5
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

# エラストテネスの篩
while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

# if (i + 1) / 2 in primeのにぶたん
def binary_search_loop(data, target):
    imin = 0
    imax = len(data) - 1
    while imin <= imax:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return True
        elif target < data[imid]:
            imax = imid - 1
        else:
            imin = imid + 1
    return False

# 累積和
lista = [0] * max
for i in prime:
    if binary_search_loop(prime, (i + 1) / 2):
        lista[i - 1] = 1
listb = [0]
for i in range(max):
    listb.append(lista[i] + listb[i])

# rまでの累積 - l - 1までの累積
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(listb[r] - listb[l - 1])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]


yn = ['Yes', 'No']
YN = ['YES', 'NO']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True

def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime


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


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def coprime(a, b):
    return gcd(a, b) == 1


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q
    MX = 10**5+1

    for i in range(Q):
        l[i], r[i] = MI()

    primes_nums = primes(MX)
    likes_2017 = [int(i % 2 == 1 and primes_nums[i] and primes_nums[(i+1)//2]) for i in range(MX)]
    likes_2017_acc = list(accumulate(likes_2017))
    # print(likes_2017)

    for i in range(Q):
        ans = likes_2017_acc[r[i]] - likes_2017_acc[l[i]-1]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc084/tasks/abc084_d
# D - 2017-like Number
import sys

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


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


def resolve():
    q = int(input())
    LR = [list(map(int, input().split())) for _ in range(q)]

    # 1であれば2017に似た整数、0であれば2017に似ていない数字
    Lile_2017 = [0] * (10 ** 5 + 1)

    # 素数判定済み配列
    prime = set()
    not_prime = set()

    # 1~100000が2017に似た数かどうか判定する
    for n in range(1, 10 ** 5 + 1):
        flg1, flg2 = False, False
        if n % 2 != 0:
            if n in prime:
                flg1 = True
            elif n in not_prime:
                flg1 = False
            else:
                flg1 = is_prime(n)
                prime.add(n) if flg1 else not_prime.add(n)

            if (n + 1) // 2 in prime:
                flg2 = True
            elif (n + 1) // 2 in not_prime:
                flg2 = False
            else:
                flg2 = is_prime((n + 1) // 2)
                prime.add((n + 1) // 2) if flg1 else not_prime.add((n + 1) // 2)

        Lile_2017[n - 1] += 1 if flg1 and flg2 else 0

    # 2017に似た数の累積和配列を作る
    Ruiseki = [0]
    for i in range(1, 10 ** 5 + 1):
        Ruiseki.append(Ruiseki[-1] + Lile_2017[i - 1])

    # クエリに答える
    for l, r in LR:
        print(Ruiseki[r] - Ruiseki[l - 1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

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


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


def resolve():
    q = int(input())
    LR = [list(map(int, input().split())) for _ in range(q)]

    Lile_2017 = [0] * (10 ** 5 + 1)
    prime = set()
    for n in range(1, 10 ** 5 + 1):
        flg1, flg2 = False, False
        if n % 2 != 0:
            if n is not prime:
                if is_prime(n):
                    flg1 = True
                    prime.add(n)
                else:
                    flg1 = False
            else:
                flg1 = True

            if (n + 1) // 2 is not prime:
                if is_prime((n + 1) // 2):
                    flg2 = True
                    prime.add((n + 1) // 2)
                else:
                    flg2 = False
            else:
                flg2 = True

        if flg1 and flg2:
            Lile_2017[n - 1] = 1

    Ruiseki = [0]
    for i in range(1, 10 ** 5 + 1):
        Ruiseki.append(Ruiseki[-1] + Lile_2017[i - 1])

    for i in range(q):
        l, r = LR[i]
        print(Ruiseki[r] - Ruiseki[l - 1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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
prime = primes(10**5)
li = [0]*(10**5)
for i in range(3,10**5,2):
    n = int((i-1)/2)
    if prime[i] and prime[int((i+1)/2)]:
        li[n] = li[n-1]+1
    else:
        li[n] = li[n-1]
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    ln = int((l-1)/2)
    rn = int((r-1)/2)
    if ln == 0:
        print(li[rn])
    else:
        print(li[rn]-li[ln-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    from itertools import accumulate
    #素数判定用の関数を定義
    #素数だったら１、素数じゃなかったら０と返す
    def main(n):
        if n==1:
            return 0
        else:
            for j in range(2,int(n**0.5)+1):
                if n%j==0:
                    return 0
            return 1

    q = int(input())
    # 要素がｑ個あって要素が全部０のリストをl格納用とr格納用で２つ作る
    l=[0]*q
    r=[0]*q
    # 入力してlとrを塗り替えていく
    for i in range(q):
        l[i],r[i]=list(map(int, input().split()))

    # 素数判定する範囲を定めるためにminとmaxとる
    lmin=min(l)
    rmax=max(r)

    # min~maxの値について素数判定を行う
    # 素数だったら０、素数じゃなかったら１が入ってるリストを作る
    sosucheck=[]
    for i in range(lmin,rmax+1):
        if i%2==0:
            sosucheck.append(0)
        else:
            if main(i)==1 and main((i+1)/2)==1:
                sosucheck.append(1)
            else:
                sosucheck.append(0)

    # 累積和のリスト作る（最初を０にしたいから最初に０を足す）
    rui=[0]+sosucheck
    rui=list(accumulate(rui))

    #出力
    for i in range(q):
        sr=r[i]-lmin+1
        sl=l[i]-lmin
        print(rui[sr]-rui[sl])
resolve()

Submission status: Accepted

Solution code:
import math

def main():
    Q = int(input())
    cnt = [0 for _ in range(10**5+1)]
    num = [False for _ in range(10**5+1)]
    
    
    for i in range(2, 10**5+1):
        for j in range(2, int(math.sqrt(i))+1):
            if(i%j==0):
                cnt[i] = cnt[i-1]
                break
        else:
            num[i] = True
            if(num[(i+1)//2]):
                cnt[i] = cnt[i-1]+1
            else:
                cnt[i] = cnt[i-1]

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

main()

Submission status: Accepted

Solution code:
# 26min
q = int(input())

length = 100010
primes = [1] * length
primes[1] = 0
for i in range(2, len(primes)):
    if primes[i] == 1:
        n = i*2
        while n < length:
            primes[n] = 0
            n += i

a = [0]*length

for i in range(len(a)):
    if i % 2 == 0:
        continue
    # 2017-like
    is2017Like = primes[i] and primes[(i+1) // 2]
    a[i] = (1 if is2017Like else 0)

accum = [0]*(length+1)

for i in range(length):
    accum[i+1] = accum[i] + a[i]

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate
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
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)
a=[]
for i in range(min_l,max_r+1):
  if i%2==0:
    a.append(0)
  else:
    if is_prime(i) and is_prime((i+1)/2):
      a.append(1)
    else:
      a.append(0)
check=[0]+a
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:
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

is_Prime=primes(10**5)
count=[]
cnt=0
for i in range(10**5+1):
  if is_Prime[i] and is_Prime[(i+1)//2]:
    cnt+=1
  count.append(cnt)

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:
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
c=[0]
ci=0
for i in range(1,10**5+1):
  if is_prime(i) and is_prime((i+1)//2):
    ci+=1
  c.append(ci)
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
for lri in lr:
  print(c[lri[1]]-c[lri[0]-1])

Submission status: Accepted

Solution code:
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
c=[0]
ci=0
for i in range(1,10**5+1):
  if is_prime(i) and is_prime((i+1)//2):
    ci+=1
  c.append(ci)
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
for lri in lr:
  print(c[lri[1]]-c[lri[0]-1])

Submission status: Accepted

Solution code:
n=10**5
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]
ps=primes(n)
likes=[-1]
from bisect import bisect_left,bisect_right
for i in ps:
    p=(i+1)//2
    if p==ps[bisect_left(ps,p)]:
        likes.append(i)
q=int(input())
qs=[map(int,input().split())for i in range(q)]
for a,b in qs:
    a=bisect_left(likes,a)
    b=bisect_right(likes,b)
    print(b-a)

Submission status: Accepted

Solution code:
q = int(input())
u = []
for i in range(q):
    u.append(list(map(int,input().split())))

import math
def sosu(n):
    k = 0
    if n == 1:
        return 0
    if n == 2:
        return 1
    elif n%2 == 0:
        return 0
    else:
        for i in range(3,math.floor(n**(0.5))+1,2):
            if n%i == 0:
                k += 1
        if k == 0:
            return 1
        else:
            return 0

v=[3]
for j in range(25000):
    if sosu(4*j+1)*sosu(2*j+1)==1:
        v.append(4*j+1)

t = []
for i in range(50000):
    if 2*i+1 in v:
        t.append(1)
    else:
        t.append(0)

s = [0]
for i in range(50000):
    s.append(t[i]+s[i])

for k in u:
    l = k[0]
    r = k[1]
    print(s[int((r+1)/2)]-s[int((l-1)/2)])