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:
PN = [i for i in range(100001)]
i = 2
while True:
    if i >= len(PN):
        break
    j = i * 2
    while True:
        if j >= len(PN):
            break
        PN[j] = 0
        j += i
    while True:
        i += 1
        if i >= len(PN):
            break
        if PN[i] != 0:
            break
PN[1] = 0
PN_2 = [0]
DPN = [0]
for i in range(1, 100001):
    if PN[i] != 0 and PN[int((PN[i] + 1) / 2)] != 0:
        PN_2.append(PN[i])
        DPN.append(DPN[i - 1] + 1)
    else:
        PN_2.append(0)
        DPN.append(DPN[i - 1])

#print(PN[1:30])
#print(PN_2[1:30])
#print(DPN[1:30])

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

Submission status: Accepted

Solution code:
import bisect
def mark(s, x):
    for i in xrange(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in xrange(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in xrange(0,n) if s[i] and i > 1]


primes = sieve(10**5)
likes = []
for i in primes:
	if primes[bisect.bisect_left(primes,(i+1)/2)] == (i+1)/2:
		likes.append(i)

cs = [0 for i in range(10**5+1)]

i = 1
j = 0

while i < 10**5+1 and j < len(likes):
	if likes[j] > i:
		cs[i] = cs[i-1]

	else:
		cs[i] = cs[i-1]+1
		j +=1
	i += 1
t = cs[i-1]
while i < 10**5+1:
	cs[i] = t
	i += 1

q = int(input())

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

Submission status: Accepted

Solution code:
import math
q = int(input())
x = []
for i in range(q):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
def so(k):
    n = True
    if k % 2 == 0 and k != 2:
      return False
    for divisor in range(2, math.floor(math.sqrt(k))+1):
      if k % divisor == 0:
        n = False           
    return n
map1 = [None for i in range(100005)]
map2 = [0 for i in range(100005)]
for i in range(2,100001):
  map1[i] = so(i)
for i in range(2,100001):
  if (map1[i] == True and map1[(i+1)//2] == True):
    map2[i] = map2[i-1] +1
  else:
    map2[i] = map2[i-1]
for a,b in x:
  print(map2[b]-map2[a-1])

Submission status: Accepted

Solution code:
import math
 
Q = int(input())
 
# 素数表
n = 100000
P = [False] * n
P[2] = True
for i in range(3, n, 2):
    k = True
    for j in range(3, int(math.sqrt(i)) + 1, 2):
        if i % j == 0:
            k = False
            break
    if k:
        P[i] = True
 
# Nと(N+1)÷2が素数か否か
a = [0] * n
for i in range(1, n, 2):
    j = (i + 1) // 2
    if P[i] and P[j]:
        a[i] = 1
# 累積和
for i in range(n - 1):
    a[i + 1] += a[i]
 
for _ in range(Q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])

Submission status: Accepted

Solution code:
from itertools import accumulate
def gen_prime(n):
    seq = list(range(2, n))
    while len(seq) > 0:
        prime = seq.pop(0)
        yield prime
        if n ** 0.5 >= prime:
            seq = [i for i in seq if not i % prime == 0]


N = 10 ** 5
primes = list(gen_prime(N + 1))
is_prime = [False] * (N + 1)
for i in primes:
    is_prime[i] = True

n_2017 = [is_prime[i] and is_prime[(i + 1) // 2] for i in range(0, N + 1)]
sum_n = list(accumulate(n_2017))
#%% query
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(sum_n[r] - sum_n[l - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p, t


@mt
def slv(Q, LR):
    N = 100000
    p, t = eratosthenes(N)
    qt = [0] * N
    for i in range(3, N):
        qt[i] = qt[i-1]
        if t[i] and t[(i+1)//2]:
            qt[i] += 1

    for l, r in LR:
        print(qt[r] - qt[l-1])


def main():
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    slv(Q, LR)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(Q, LR):
    N = 100000
    p = eratosthenes(N)
    qt = [0] * N
    for i in range(2, N):
        qt[i] = qt[i-1]
        if i % 2 == 0:
            continue

        q = (i+1)//2
        qi = bisect.bisect_left(p, q)
        ii = bisect.bisect_left(p, i)
        if qi != len(p) and p[qi] == q and ii != len(p) and p[ii] == i:
            qt[i] += 1

    for l, r in LR:
        print(qt[r] - qt[l-1])
    # ans = 0
    # return ans


def main():
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    # print(slv(Q, LR))
    slv(Q, LR)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

maxp = 100100

allPrimes = [1]
like2017 = []
primes_list = [0 for _ in range(maxp+1)]
import bisect

def isPrimeNum(num):
    if num in allPrimes:
        return True
    else:
        return False

def initPrimes(ma):
    furui = {i:0 for i in range(2,ma+1)}

    primes_list[1] = 1

    for i in range(2,ma):
        if furui[i] == 0:
            
            if i > 2 and primes_list[(i+1)//2] == 1:
                like2017.append(i)

            primes_list[i] = 1

            for h in range(1,ma):
                index = i * h
                if index>ma:
                     break
                furui[index] = 1




initPrimes(maxp)

count = 0
for _ in range(N):
    l,r = [int(x) for x in input().split()]

    f = bisect.bisect_left(like2017,l)
    t = bisect.bisect_right(like2017,r)

    print(t-f)

Submission status: Accepted

Solution code:
from itertools import accumulate, count, islice, takewhile
 
def eratosthenes():
    d = {}
    for q in count(2):
        p = d.pop(q, None)
        if p:
            x = next(x for x in count(q + p, p) if x not in d)
            d[x] = p
        else:
            yield q
            d[q*q] = q

def likes():
    xs = set()
    for p in eratosthenes():
        if p in xs:
            yield p
        xs.add(2*p - 1)

likeset = set(takewhile(lambda n: n <= 100000, likes()))
onehot = (i in likeset for i in range(100001))
likecounts = list(accumulate(onehot))

q = int(input())
lrs = [[int(x) for x in input().split()] for _ in range(q)]

for l, r in lrs:
    print(likecounts[r+1] - likecounts[l-1])

Submission status: Accepted

Solution code:
tf = [True] * 100001
tf[0] = tf[1] = True
for i in range(2, 320):
  if tf[i]:
    for j in range(i ** 2, 100001, i):
      tf[j] = False

tf2 = [False] * 100001
for i in range(3, 100001):
  if tf[i] and tf[(i + 1) // 2]:
    tf2[i] = True

count = []
acc = 0
for i in range(100001):
  acc += tf2[i]
  count.append(acc)

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

Submission status: Accepted

Solution code:
MAX_N = 10 ** 5
p_lst = [0 for i in range(MAX_N+1)]


def is_prime():
    a = [0 for i in range(MAX_N+1)]
    for i in range(2, MAX_N+1):
        for j in range(2*i, MAX_N+1, i):
            a[j] += 1

    for i in range(2, MAX_N+1):
        if a[i] == 0:
            p_lst[i] = 1


def main():
    q = int(input())

    is_prime()
    s, idx = [0 for i in range(MAX_N+1)], 0
    for i in range(2, MAX_N+1):
        if p_lst[i] == 1 and p_lst[(i+1)//2] == 1:
            s[i] = s[i-1] + 1
        else:
            s[i] = s[i-1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    #prime_list = []
    like2017_list = []
    for prime in range(3,num+1,2):
#        if isPrime[prime]:
#            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    #input
#    Q1 = 1
#    LR1 = [[3,7]]
#    
#    Q2 = 4
#    LR2 = [[13, 13],
#                [7, 11],
#                [7, 11],
#                [2017, 2017]]
#    
#    
#    Q = Q2
#    LR = LR2
    
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    # judge
    csum = [0]*(MAX_Q+1)
    i = 0
    cnt = 0
    for like2017 in like2017_list:
        while i < like2017:
            csum[i] = cnt
            i += 1
        cnt += 1
    for i in range(like2017_list[-1], MAX_Q+1):
        csum[i] = cnt
        
    
    for i in range(Q):
        print(csum[LR[i][1]] - csum[LR[i][0]-1])


    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prime(n):
	prime = [2,3,5]
	for i in range(6,n+1):
		check = True
		for k in range(2,int(i**0.5)+1):
			if i%k == 0:
				check = False
				break
		if check:
			prime.append(i)
	return prime

prime = prime(100000)
data = dict()
for i in range(1,100001):
	data[i] = 0
for k in range(len(prime)):
	data[prime[k]] = 1

anotherdata = dict()
for i in range(0,100001):
	anotherdata[i] = 0
counter = 1
for k in range(1,len(prime)):
	if data[(prime[k]+1)/2] == 1:
		anotherdata[prime[k]] = counter
		counter += 1
anotherdata[1] = 0
anotherdata[2] = 0
for e in range(3,100001):
	if anotherdata[e] == 0:
		anotherdata[e] = anotherdata[e-1]

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

Submission status: Accepted

Solution code:
def get_prime_list(n):
    L = tuple(range(2,n+1))
    for i in range(2,int((n+1)**0.5)):
        if i not in L:
            continue
        L = tuple(j for j in L if j <= i) + tuple(j for j in L if j > i and j % i != 0)
    return L

Q = int(input())
lr = [tuple(map(int,input().split())) for _ in range(Q)]
prime_list = get_prime_list(100000)
like_num = tuple(i for i in prime_list if (i+1)//2 in prime_list)
L = [0] * 100002
for i in range(3,100001,2):
    if i in like_num:
        L[i] = L[i-2]+1
    else:
        L[i] = L[i-2]
for l,r in lr:
    print(L[r]-L[l-2])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 20 16:39:29 2018

@author: Yuya
"""

import numpy
#N = range(1, 100001, 2)

N =list(range(3, 100001, 2))

for i in range(49999):
    flag = -1
    Len_N = len(N)
    for j in range(Len_N-1, i, -1):
        if N[j]%N[i] == 0:
            del N[j]
            flag = 1
    if flag < 0:
        break

N = [2]+N

for i in range(len(N)-1, 0, -1):
    if not (N[i]+1)//2 in N:
        del N[i]
    
N_2017 = N[1:]


Sum_N = [0]*100000

for i in range(len(N_2017)):
    Sum_N[N_2017[i-1]] = 1
    
res = list(numpy.cumsum(Sum_N))

Q = int(input())

L_Q = [0]*Q
R_Q = [0]*Q

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

for i in range(Q):
    print(res[R_Q[i]]-res[L_Q[i]-1])

Submission status: Accepted

Solution code:
import math

Q = int(input())

# 素数表
n = 100000
P = [False] * n
P[2] = True
for i in range(3, n, 2):
    k = True
    for j in range(3, int(math.sqrt(i)) + 1, 2):
        if i % j == 0:
            k = False
            break
    if k:
        P[i] = True

# Nと(N+1)÷2が素数か否か
a = [0] * n
for i in range(1, n, 2):
    j = (i + 1) // 2
    if P[i] and P[j]:
        a[i] = 1
# 累積和
for i in range(n - 1):
    a[i + 1] += a[i]

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

Submission status: Accepted

Solution code:
class Prime:
    def __init__(self,number):#N以下の素数
        self.jud=[True]*(number+5)
        self.pri=[]
        self.jud[0]=False
        self.jud[1]=False
        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2,(number)//i+1):
                    self.jud[i*j]=False
    
    def judge(self,x):
        return self.jud[x]
    
    def decom(self,x):
        s=x
        a =[]
        if s==1:
            return a
        while s>1:
            for p in self.pri:
                if s%p==0:
                    a.append(p)
                    s=s//p
                    break
        return a
            

A=Prime(10**5)
Q=int(input())
Que=[[int(i) for i in input().split()] for i in range(Q)]
cou=[0]*(10**5+1)
for i in range(3,10**5+1):
    if A.judge(i) and A.judge((i+1)//2):
        cou[i]=cou[i-1]+1
    else:
        cou[i]=cou[i-1]
ans=[]
for l,r in Que:
    ans.append(cou[r]-cou[l-1])
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import math
Q=int(input())
querys = [list(map(int,input().split())) for x in range(Q)]
large = max(q[1] for q in querys)
like2017 = [0]*(large+1)

#siever
cands = [False if (5 < i and (i%2)*(i%3)*(i%5) == 0) or (i < 2) or (i == 4) else True for i in range(large+1)]
if 5 <= large:
  for i in range(6,int(math.sqrt(large)+1)):
    if cands[i]:
      for j in range(i*i,large+1,i):
        if cands[j]:
          cands[j] = False

#find 2017-like-number          
for x in range(large+1):
  if cands[x] and cands[(x+1)//2]:
    like2017[x] = 1
for y in range(1,large+1):
  like2017[y] += like2017[y-1]

for q in querys:
  print(like2017[q[1]]-like2017[q[0]-1])

Submission status: Accepted

Solution code:
def main():
    Q = int(input())
    L = [0 for _ in range(Q)]
    R = [0 for _ in range(Q)]
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    N = 100000
    sosu = [1 for _ in range(N)]
    sosu[0] = 0
    for i in range(1,int(N**0.5)):
        k = i+1
        if sosu[i] == 1:
            j = k + k
            while j <= N:
                sosu[j-1] = 0
                j = j+k
    like = [0 for _ in range(N)]
    for i in range(2, N, 2):
        if sosu[i]==1 and sosu[(i+2)//2-1]==1:
            like[i] = 1
    like_wa = [0 for _ in range(N+1)]
    for i in range(N):
        like_wa[i+1] = like_wa[i] + like[i]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not isPrime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            isPrime[j] = False
    return isPrime

Q = int(input())
L = [0]
isPrime = makePrimeChecker(100000)
for i in range(1, 100000):
    if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
        L.append(L[-1] + 1)
    else:
        L.append(L[-1])
for i in range(Q):
    l, r = map(int, input().split())
    print(L[r] - L[l-1])

Submission status: Accepted

Solution code:
Q = int(input())
#エラトスてねす
que=[]     
for i in range(Q):
    l,r = map(int,input().split())
    que.append((l,r))


M = 10**5+10
prime=[True]*M
prime[0]=False
prime[1]=False
for i in range(2,M):
    if prime[i]:
        for j in range(2,(M-1)//i+1):
            prime[i*j]=False
con=[0]*M
for j in range(3,M):
    if prime[j] and prime[(j+1)//2]:
        con[j] = con[j-1]+1
    else:
        con[j]=con[j-1]


ans =[]
for i in range(Q):
    l,r = que[i]
    ans.append(con[r]-con[l-1])
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
isPrime = [True for i in range(100001)]
isPrime[0] = False
isPrime[1] = False

for i in range(2, 100001):
    if isPrime[i]:
        j = 2
        while i*j <= 100000:
            isPrime[i*j] = False
            j += 1

isSimilar = [True for i in range(100001)]
for i in range(100001):
    if isPrime[i] and isPrime[(i+1)//2]:
        pass
    else:
        isSimilar[i] = False

cnt = [0 for i in range(1, 100010)]
for i in range(1, 100001):
    cnt[i] = cnt[i-1] + [0, 1][isSimilar[i]]

q = int(input())
lrs = list()
for i in range(q):
    lrs.append(list(map(int, input().split())))

for l, r in lrs:
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
isPrime = [True for i in range(100010)]
# エラトステネスの篩で素数判定
isPrime[0]=isPrime[1]=False
for i in range(2,100010):
    if isPrime[i]:
        j=2
        while i*j<=100000:
            isPrime[i*j]=False
            j+=1
# isSimilar
isSimilar = [True for i in range(100010)]
for i in range(100010):
    if isPrime[i] and isPrime[(i+1)//2]:
        isSimilar[i]=True
    else:
        isSimilar[i]=False
# 累積和を取ります
cnt = [0 for i in range(100010)]
for i in range(1, 100010):
    cnt[i] = cnt[i-1] + [0, 1][isSimilar[i]]
# 入力
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    # cnt[r] - cnt[l-1]が答えです
    print(cnt[r] - cnt[l-1])

Submission status: Accepted

Solution code:
q = int(input())
l = list(range(2, 10**5+1))
prime = [1]*(10**5+1)
prime[0], prime[1] = 0, 0
temp = [0]*(10**5+1)
counts = [0]*(10**5+1)
ans = 0
for i in range(2, int((10**5)**0.5) + 1):
  if not prime[i]:
    continue

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

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

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

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

Submission status: Accepted

Solution code:
def eratosthenesAray(N):
    prime=[True]*(N+1)
    prime[0]=False
    prime[1]=False
    for i in range(2,N+1):
        if prime[i]:
            for j in range(i+i,N+1,i):
                prime[j]=False
    return prime

N=int(input().strip())
primes=eratosthenesAray(100000)
ruiseki=[0]*100001
for i in range(1,100001):
    ruiseki[i]=ruiseki[i-1]
    if primes[i] and primes[(i+1)//2]:
        ruiseki[i]+=1
for i in range(N):#N
    l,r=map(int,input().split())
    print(ruiseki[r]-ruiseki[l-1])

Submission status: Accepted

Solution code:
List = [True for x in range(100001)]
c = [0 for x in range(100001)]
#素数ならば、True
List[0] = False
List[1] = False
List[2] = True
for i in range(2,100001):
    if(List[i] == True):
        for j in range(i+i,100001,i):
            List[j] = False
#1print(List)
for i in range(3,100001, 2):
    if(List[i] and List[int((i+1)/2)]):
        # print('hoge')
        c[i] += 1
# print(c)
for i in range(100001):
    c[i] += c[i-1]
#print(c)
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    print(c[r] - c[l-1])

Submission status: Accepted

Solution code:
p = [True for _ in range(10**5)]
p[0] = False
p[1] = False
for i in range(4,10**5,2):
    p[i] = False
for i in range(3,10**5,2):
    if p[i]:
        d = 2
        while i*d < 10**5:
            p[i*d] = False
            d += 1
n = [0 for _ in range(10**5)]
for i in range(1,10**5,2):
    n[i] = n[i-2]
    if p[i] and p[(i+1)/2]:
        n[i] = n[i-2] + 1

q = int(raw_input())
for _ in range(q):
    l,r = map(int, raw_input().split())
    k = n[r] - n[l]
    if l > 1 and n[l] > n[l-2]:
        k += 1
    print k

Submission status: Accepted

Solution code:
MAX_SIZE = 10**5 + 1
is_prime = [True] * MAX_SIZE
is_prime[0] = False
is_prime[1] = False
for i in range(MAX_SIZE):
    if is_prime[i]:
        for j in range(2*i, MAX_SIZE, i):
            is_prime[j] = False
dp = [0] * MAX_SIZE
for i in range(1, MAX_SIZE):
    dp[i] = dp[i-1] + int(is_prime[i] & is_prime[(i+1) / 2])
q = input()
for i in range(q):
    l, r = map(int, raw_input().split())
    print dp[r] - dp[l-1]

Submission status: Accepted

Solution code:
import numpy as np

q = int(input())

params = [[int(el) for el in input().split()] for _ in range(q)]


def get_nearst(max):
    primes = [True for i in range(max+1)]

    for i in range(2, max):
        if primes[i]:
            for j in range(i+i, max+1, i):
                primes[j] = False

    primes[0] = False
    primes[1] = False

    neast = [False for i in range(max)]

    for i in range(3, max+1, 2):
        if primes[i] and primes[int((i+1)/2)]:
            neast[i] = True

    return tuple(neast)


primes = get_nearst(max=10**5)

ruise = np.cumsum(primes)

# for index, el in enumerate(ruise[:100]):
#     print(index, el)

for l, r in params:
    if r == l:
        print(int(primes[r]))
    else:
        print(ruise[r]-ruise[l-1])

Submission status: Accepted

Solution code:
q=int(input())
lr=[list(map(int, input().split())) for i in range(q)]
l,r=[],[]
for a in lr:
    l.append(a[0])
    r.append(a[1])
mr=max(r)
x = [True]*(mr+1)
x[0]=False
x[1]=False

for i in range(mr+1):
    if x[i]:
        for j in range(2*i, mr+1, i):
            x[j] = False
c=[0]*(mr+1)
for i in range(1,mr+1):
    if x[i] and x[(i+1)//2]:
        c[i] = c[i-1]+1
    else:
        c[i] = c[i-1]
for i in range(q):
    print(c[r[i]]-c[l[i]-1])

Submission status: Accepted

Solution code:
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        for j in range(2* i, 100001, i):
            work[j] = False


csum = [0] * 100001
index = 0
for i in range(1, 100001):
    if work[i] and work[(i+1)//2]:
        csum[i] = csum[i - 1] + 1
    else:
        csum[i] = csum[i - 1]

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

Submission status: Accepted

Solution code:
from collections import Counter
P = [0] * 100001
Q = [0] * 100002
P[0] = 1
P[1] = 1

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

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

for k in range(3, 100000, 2):
    if P[k] == 0 and P[(k + 1) // 2] == 0:
        Q[k] = 1
for l in range(100000):
    Q[l+1] += Q[l]

for m in range(n):
    l, r = num[m][0], num[m][1]
    print(Q[r] - Q[l-1])

Submission status: Accepted

Solution code:
N = 100001
A,B = [True]*N,[0]*N
A[0],A[1] = False,False
for i in range(2,N):
    if A[i]:
        for j in range(i*2,N,i):
            A[j] = False
c=0
for i in range(3,N):
    if A[i] and A[(i+1)//2]:
        c += 1
    B[i] = c
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(B[r]-B[l-1])

Submission status: Accepted

Solution code:
Q = int(input())

MAX = 10**5
is_primes = [True for _ in range(MAX+1)]
is_primes[0] = False
is_primes[1] = False

for i in range(2, MAX):
    if is_primes[i]:
        for j in range(2*i, MAX, i):
            is_primes[j] = False

count = 0
count_2017 = [0, 0]
for i in range(3, MAX, 2):
    if is_primes[i]:
        if is_primes[(i+1)//2]:
            count += 1
    count_2017.append(count)

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

Submission status: Accepted

Solution code:
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return s
    
A = sieve(100000)

A[0] = A[1] = False
#A = [False]+A

B=[0]*100002

for i in range(100000):
    if A[i] and (i+1)%2 == 0:
        if A[int((i+1)/2)]:
            B[i] = B[i-1]+1
        else:
            B[i] = B[i-1]          
    else:
        B[i] = B[i-1]
        
q = int(input())

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

Submission status: Accepted

Solution code:
q = int(input())
a = [[int(i) for i in input().split()] for i in range(q)]
prime = [True]*100000
prime[0],prime[1] = False,False
for i in range(2, 317):
	if not prime[i]: continue
	for j in range(i*2,100000,i): prime[j] = False
y = [0]
for i in range(3,10**5,2):
	if prime[i] and prime[(i+1)//2]: y.append(y[-1]+1)
	else: y.append(y[-1])
for i in a:
	print(y[(i[1]-1)//2]-y[max((i[0]-3)//2,0)])

Submission status: Accepted

Solution code:
import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])

Submission status: Accepted

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

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%prime[m-1] != 0,prime[m:])
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


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

Submission status: Accepted

Solution code:
import math
def is_prime(x):
    if x < 2: return False  # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True  # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False  # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    pri = 7
    step = 4
    while pri <= math.sqrt(x):
        if x % pri == 0: return False

        pri += step
        step = 6 - step

    return True

Q = int(input())

prime = [0] * 100002
prime[0] = 0
prime[1] = 0
prime[2] = 0
num = 3

while num < 100002:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2):
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
MAX=100001
array=[True for i in range(MAX)]
array[1]=False
similar=[True for i in range(MAX)]

for i in range(2, MAX):
	if array[i]:
		for j in range(2, int(MAX/i)+1):
			if(j*i < MAX):
				array[i*j]=False
c=[0 for i in range(MAX)]
count=0

for i in range(2, MAX):
	if array[i] and array[int((i+1)/2)]:
		count+=1

	c[i]=count

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

Submission status: Accepted

Solution code:
import math
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def calc_sosus(max_num):
	IsPrimes = [True] * (max_num + 1)
	IsPrimes[0] = False
	IsPrimes[1] = False
	for min_i in range(2, int(math.sqrt(max_num)) + 1):
		if IsPrimes[min_i]:
			for num in range(min_i*min_i, max_num+1, min_i):
				IsPrimes[num] = False
	return IsPrimes

IsPrimes = calc_sosus(max_num)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (IsPrimes[i]) & (((i+1) % 2)==0) & (IsPrimes[(i+1)/2]): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

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

Submission status: Accepted

Solution code:
import math

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

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
cut_root = math.sqrt(M+1)
for prime in primes:
	if prime > cut_root:
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0
similar_2017 = [0 for _ in range(M+1)]
similar_2017[3] = 1
for i in range(5, M+1, 4):
	if primes[i] != 0:
		if primes[(i+1)//2] != 0:
			similar_2017[i] = 1
similar_sum = [0 for _ in range(M+1)]
for i in range(1,M+1):
	if similar_2017[i] == 1:
		similar_sum[i] = similar_sum[i-1] + 1
	else:
		similar_sum[i] = similar_sum[i-1]

for l, r in li:
	print(similar_sum[r] - similar_sum[l-1])