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: Time Limit Exceeded

Solution code:
#coding:utf-8

pp = [341,561,645,1105,1387,1729,1905,2047,2465,2701,
               2821,3277,4033,4369,4371,4681,5461,6601,7957,8321,
               8481,8911]

def is_prime(q):
    p = int(abs(q))
    if p == 2: return True
    if p < 2 or p&1 == 0: return False
    for k in pp:
        if q == k:
            return False
    return pow(2, p-1, p) == 1

q = int(input())
e = [[int(i) for i in input().split()] for i in range(q)]

ct = 0

for j in range(q):
    for i in range(e[j][0], e[j][1]+1, 2):
        if is_prime(i)==True and is_prime((i+1)/2)==True:
            ct = ct + 1
    print(ct)
    ct = 0

Submission status: Time Limit Exceeded

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

def isPrime(n):
  if n == 2:
    return True
  if n % 2==0 or n == 1:
    return False
  j = 3
  while j <= math.sqrt(n):
    if n % j == 0:
      return False
    j += 2
  return True

C = []
for i in range(q):
  ran = list(map(int, input().split()))
  for i in range(q):
    if ran[0] % 2 == 0:
        j = ran[0]+1
    j = ran[0]
    count = 0
    while j <= ran[1] :
      if isPrime(j) and isPrime((j+1)//2):
        count += 1
      j += 2
  C.append(count)

for i in range(q):
  print(C[i])

Submission status: Time Limit Exceeded

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でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
alst = []

for i in range(n):
    s = input().split()
    l = int(s[0])
    r = int(s[1])
    ans = 0
    
    for x in range(l, r+1, 2):
        ans += 1 if (is_prime(x) and is_prime((x+1)//2)) else 0
    
    alst.append(ans)



for i in range(n):
    print(alst[i])

Submission status: Time Limit Exceeded

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
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
for k in range(Q):
    c=0
    for n in range(l[k],r[k]+1,2):
        if P[n] and P[(n+1)//2]:
           c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

q=int(input())
c=0

for i in range(q):
    n=list(map(int,input().split(" ")))
    for j in range(n[0],n[1]+1,2):
        if is_prime(j):
            if is_prime((j+1)/2):
                c+=1
    print(c)
    c=0

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

for _ in range(int(input())):
    c = 0
    a, b = map(int, input().split())
    for i in range(a, b+1):
        if is_prime(i) and is_prime((i+1)/2):
            c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
    q = int(input())
    C = []
    for _ in range(q):
        c = 0
        l, r = map(int, input().split())
        for x in range(l, r + 1, 2):
            c1 = 0
            for y in range(1, x + 1):
                if x % y == 0:
                    c1 += 1
            if c1 == 2:
                c2 = 0
                for z in range(1, (x + 1) // 2 + 1):
                    if (x + 1) // 2 % z == 0:
                        c2 += 1
                if c2 == 2:
                    c += 1
        C.append(c)

    for x in range(len(C)):
        print(C[x])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

MAXN = 100001
isPrime = [True for x in range(0, MAXN)]

def findPrime():
    isPrime[1] = False
    for i in range(2, MAXN):
        if isPrime[i]:
            for j in range(i + i, int(math.sqrt(MAXN)) + 1, i):
                isPrime[j] = False

findPrime()

Q = int(input())

for i in range(Q):
    temp = 0
    l, r = map(int, input().split())
    for j in range(l, r + 1, 2):
        if isPrime[j] and isPrime[(j+1)//2]:
            temp += 1
    print(temp)

Submission status: Time Limit Exceeded

Solution code:

def is_prime(q):
    if q == 2:
        return True
    return pow(2, q-1, q) == 1

n = input()
for _ in xrange(n):
    s = 0
    a, b = map(int, raw_input().split())
    for i in xrange(a, b+1):
        if is_prime(i) and is_prime((i+1)/2):
            s += 1
    print s

Submission status: Time Limit Exceeded

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

n = input()
for _ in xrange(n):
    s = 0
    a, b = map(int, raw_input().split())
    for i in xrange(a, b+1):
        if is_prime(i) and is_prime((i+1)/2):
            s += 1
    print s

Submission status: Time Limit Exceeded

Solution code:
import math

def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

def my_chk(num):
    if is_prime(num) and is_prime((num+1)*0.5):
        return 1
    else:
        return 0
    
if __name__ == '__main__':
    q = int(input())
    ans = []
    for i in range(q):
        info = list(map(int,input().split(" ")))
        chk_list = [ele for ele in range(info[0],info[1]+1,2)]
        temp = list(map(my_chk,chk_list))
        ans.append(sum(temp))
    for ele in ans:
        print(ele)

Submission status: Time Limit Exceeded

Solution code:
MAXN = 100001
isPrime = [True for x in range(0, MAXN)]

def findPrime():
    isPrime[1] = False
    for i in range(2, MAXN):
        if isPrime[i]:
            for j in range(i + i, MAXN, i):
                isPrime[j] = False

findPrime()

Q = int(input())

for i in range(Q):
    temp = 0
    l, r = map(int, input().split())
    for j in range(l, r + 1, 2):
        if isPrime[j] and isPrime[(j+1)//2]:
            temp += 1
    print(temp)

Submission status: Time Limit Exceeded

Solution code:
p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
e = []
for i in xrange(100000):
    s = False
    if p[i] and p[(i + 1) / 2]:
        s = True
    e.append(s)
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print sum(e[l: r + 1])

Submission status: Time Limit Exceeded

Solution code:
prime = [True]*(10**5+1)
prime[0] = False
prime[1] = False

for a in range(2,318): # >>> gmpy2.isqrt(10**5+1) -> mpz(316)
  if prime[a] == False:
    continue
  else:
    for b in range(a*2,10**5+1,a): 
      prime[b] = False
"""
print prime
import gmpy2

for a in range(0,10**5+1):
  if prime[a] != gmpy2.is_prime(a):
    print "NO"
    print a
"""
ans = [False]*(10**5+1)
for a in range(3,10**5+1,2):
  if prime[a] == True and prime[(a+1)/2] == True:
    ans[a] = True

q = int(raw_input())
for a in range(q):
  l,r = map(int,raw_input().split(" "))
  print ans[l:r+1].count(True)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

n = 10 ** 5
is_prime = [True for i in range(n)]

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

for i in range(Q):
    l, r = map(int, input().split())
    rec = 0
    for j in range(l, r + 1):
        if is_prime[j] and is_prime[(j + 1) // 2]:
            rec += 1
    print(rec)

Submission status: Time Limit Exceeded

Solution code:
p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    for i in xrange(l, r + 1):
        if i & 1:
            if p[i] and p[(i + 1) / 2]:
                c += 1
    print c

Submission status: Time Limit Exceeded

Solution code:
primes = [0, 0] + [1] * 99999
for i in range(2, 317):
    if primes[i]:
        for j in range(i*i, 100001, i):
            primes[j] = 0

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(sum(primes[i] and primes[(i+1)//2] for i in range(l, r+1, 2)))

Submission status: Accepted

Solution code:
import bisect
Q = int(input())
lsQ = []
for i in range(Q):
    l,r = map(int,input().split())
    lsQ.append([l,r])
def prime(N):
    lsprime = [0,0]+[1 for i in range(N-1)]
    lsprime2 = []
    for i in range(N+1):
        if lsprime[i] == 0:
            continue
        lsprime2.append(i)
        k = i
        while i <= N:
            lsprime[i] = 0
            i += k
    return lsprime2

primels = prime(10**5)
primeset = set(primels)
lssim = []
for i in primels:
    x = (i+1)//2
    if x in primeset:
        lssim.append(i)
for i in range(Q):
    ans = bisect.bisect(lssim,lsQ[i][1])-bisect.bisect_left(lssim,lsQ[i][0])
    print(ans)

Submission status: Accepted

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

#l = list(map(int, input().split()))
#import numpy as np
#arr = np.array([int(i) for i in input().split()])
'''
a,b=[],[]
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

def premf(n):
    #前処理
    #minfactor:複数の素因数分解を高速(O(Q*logA_max))に行う,indexはその整数
    #return resで素数リスト(eratosthenes),MinFactorで前処理用リスト返す
    IsPrime=[False]+[False]+[True]*(n-1)

    res=[]
    for j in range(4,n+1,2):
        IsPrime[j]=False
    for i in range(1,n+1,2):
        if IsPrime[i]:
            for j in range(i*2,n+1,i):
                    IsPrime[j]=False

            if IsPrime[(i+1)//2]:
                res.append(i)
        
                
    
    return res

q=int(input())
n=10**5
res=premf(n)
a=[0]*(10**5+1)#1-index
t=0
#print(res)
for i in range(len(res)):
    t+=1
    a[res[i]]=t
for i in range(10**5):
    if a[i+1]==0:
        a[i+1]=a[i]
#print(a[:20])
for i in range(q):
    l,r=map(int,input().split())
    print(a[r]-a[l-1])

Submission status: Accepted

Solution code:
import math
q=int(input())
num=[0]*(10**5+5)
ans=[0]*(10**5+5)
num[2]=1
for i in range(3,10**5+2,2):
    yn=0
    for j in range(2,int(math.sqrt(i))+1):
        if i%j==0:
            yn=1
            break
    if yn==0:
        num[i]=1
        if num[(i+1)//2]==1:
            ans[i]=1
for i in range(1,len(num)):
    ans[i]=ans[i-1]+ans[i]
for i in range(q):
    l,r=map(int,input().split())
    print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
import numpy as np
import bisect
def sieve_of_eratosthenes(n):
    max = int(np.sqrt(n))
    seachList = [i for i in range(2,n+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        prm = seachList[0]
        seachList = [i for i in seachList if i%prm != 0]
    primeNum.extend(seachList)
    return primeNum


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

prime_list = sieve_of_eratosthenes(max(r))

ruiseki = [0]*len(prime_list)
for i in range(len(prime_list)):
    if (prime_list[i]+1)//2 in prime_list:
        ruiseki[i] += 1 + ruiseki[i-1]
    else:
        ruiseki[i] = ruiseki[i-1]

ruiseki.insert(0,0)

for i in range(Q):
    ans = 0
    ans = ruiseki[bisect.bisect_right(prime_list,r[i])] - ruiseki[bisect.bisect_left(prime_list,l[i])]
    print(ans)

Submission status: Accepted

Solution code:
import bisect

N = 10 ** 5
primes = [True] * (N + 1)
primes[0] = primes[1] = False
for i in range(2, int(len(primes) ** 0.5 + 1)):
    for j in range(i + i, len(primes), i):
        primes[j] = False
primes = [i for i in range(len(primes)) if primes[i]]
targets = [x for x in primes if (x + 1) // 2 in primes]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    x = bisect.bisect_left(targets, l)
    y = bisect.bisect_right(targets, r)
    print(y - x)

Submission status: Accepted

Solution code:
def isPrime(n):
    # nの素数判定
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


p = [False]*(10**5+1)
c = [0]*(10**5+1)

for i in range(2, len(p)):
    p[i] = isPrime(i)
    c[i] = c[i-1]
    if i % 2 == 1 and p[i] and p[i//2+1]:
        c[i] += 1

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

Submission status: Accepted

Solution code:
import bisect

def sieve(n):
    is_prime =[1]*n
    is_prime[0]=0

    for i in range(2,int((n**0.5)//1+2)):
        if is_prime[i-1]:
            j=i*2
            while j<=n:
                is_prime[j-1]=0
                j+=i
    table=[i for i in range(3,n+1) if is_prime[i-1] and is_prime[i//2]]
    return table

q=int(input())
L=sieve(10**5+1)
ans=[]

for i in range(q):
    l,r=map(int,input().split())
    ans.append(bisect.bisect_right(L,r)-bisect.bisect_left(L,l))

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

Submission status: Accepted

Solution code:
class Eratosthenes():  # エラトステネスの篩
    def __init__(self, N):  # 素数リスト生成 O(n*log(log n))
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N ** 0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i ** 2, N + 1, i):
                self.fact[j] = i
        self.prime = set(i for i in range(2, N + 1) if i == self.fact[i])


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

p = Eratosthenes(10 ** 5).prime
acc = [0]
for i in range(1, 10 ** 5, 2):
    tmp = (i in p) and ((i + 1) // 2 in p)
    acc.append(acc[-1] + tmp)

for l, r in lr:
    ans = acc[r // 2 + 1] - acc[l // 2]
    print(ans)

Submission status: Accepted

Solution code:
q = int(input())

n = 10**6
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

P = [0]*(10**6)

for i in range(1,10**6 - 1):
	if is_prime[i+1] == True and is_prime[(i+2)//2] == True:
		P[i+1] = P[i] + 1
	else:
		P[i+1] = P[i]

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

Submission status: Accepted

Solution code:
def Sieve_of_Eratosthenes(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
  #return [i for i in range(n+1) if is_prime[i]]

def is_2017like(n):
  return is_prime[n] and is_prime[(n+1)//2]

is_prime = Sieve_of_Eratosthenes(10**5)
check = [is_2017like(n) for n in range(10**5 + 1)]
ans = [0]
for i in range(1, 10**5 + 1):
  if check[i]:
    ans.append(ans[-1] + 1)
  else:
    ans.append(ans[-1])

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

Submission status: Accepted

Solution code:
import math


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

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

    return True


q = int(input())
l = []
r = []
for i in range(q):
    ll, rr = map(int, input().split())
    l.append(ll)
    r.append(rr)

dp = [0 for _ in range(10**5 + 5)]
dpsum = [0 for _ in range(10**5 + 5)]

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

for i in range(q):
    print(dpsum[r[i]] - dpsum[l[i] - 2])

Submission status: Accepted

Solution code:
import itertools

Q = int(input())
l = [0 for q in range(Q)]
r = [0 for q in range(Q)]
for q in range(Q):
  l[q], r[q] = map(int, input().split(' '))
max_r = max(r)
prime_numbers = [True for n in range(max_r+1)]
similar_numbers = [False for n in range(max_r+1)]
 
prime_numbers[0], prime_numbers[1] = False, False    # 1 is not a prime number
for divisor in range(2, max_r//2 + 1):
  if prime_numbers[divisor]:
    for multipler in range(2, max_r//divisor + 1):
      prime_numbers[divisor * multipler] = False
      
for N in range(1, max_r + 1, 2):
  if prime_numbers[N] and prime_numbers[(N+1)//2]:
    similar_numbers[N] = True
accumulate_sim_nums = list(itertools.accumulate(map(int, similar_numbers)))
    
for q in range(Q):
  print(accumulate_sim_nums[r[q]]-accumulate_sim_nums[l[q]-1])

Submission status: Accepted

Solution code:
def ERTS(N):
    table = [True]*(N+1)
    table[0], table[1] = False, False
    n = 2
    while n < N**0.5+1:
        if n:
            for i in range(n*2, N+1, n):
                table[i] = False
        n += 1
    return table

table = ERTS(10**5)
prime = []
for i in range(10**5+1):
    if table[i]:
        prime.append(i)

lst = []       
for p in prime:
    if table[(p+1)//2]:
        lst.append(p)

import bisect
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    l = bisect.bisect_left(lst, L)
    r = bisect.bisect(lst, R)
    print(r - l)

Submission status: Accepted

Solution code:
import numpy as np

def isPrimeNum(x):
    if type(x) is not int: return False
    if x <= 1: return False
    if x <= 3: return True
    max = int(np.sqrt(x))
    for i in range(2, max+1):
        if x % i == 0: return False
    return True
    
def isNumLike2017(x):
    if isPrimeNum(x) == False: return False
    if isPrimeNum(int((x+1)/2)) == False: return False
    return True
        
N = 10**5
X = np.zeros(N+1, dtype='int64')
for i in range(1, N+1):
    if isNumLike2017(i): X[i] += 1
X = X.cumsum()

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

Submission status: Accepted

Solution code:
import numpy as np

def isPrimeNum(x):
    if type(x) is not int: return False
    if x <= 1: return False
    if x <= 3: return True
    max = int(np.sqrt(x))
    for i in range(2, max+1):
        if x % i == 0: return False
    return True
    
def isNumLike2017(x):
    if isPrimeNum(x) == False: return False
    if isPrimeNum(int((x+1)/2)) == False: return False
    return True
        
N = 10**5
X = np.zeros(N, dtype='int64')
for i in range(1, N+1):
    if isNumLike2017(i): X[i-1] += 1
X = X.cumsum()

Q = int(input())
for _ in range(Q):
    l, r = input().split()
    l, r = int(l), int(r)
    if l == 1: L = 0
    else: L = X[l-2]
    R = X[r-1]
    print(R - L)

Submission status: Accepted

Solution code:
def f():    
    dp = [1]*(10**5+1) #エラトステネスの篩
    dp[0],dp[1] = 0, 0
    for i in range(2, 10**5+1):
        if dp[i] == 0:
            continue
        j = i
        while j + i <= 10**5:
            j += i
            if dp[j] == 1:
                dp[j] = 0
    
    ni = [0]*(10**5+1) #2012_like check
    for i in range(2, 10**5+1):
        if dp[i] == 1 and dp[(i+1)//2] == 1:
            ni[i] = 1
    
    ru = [0]*(10**5+1)
    for i in range(1, 10**5+1):
        ru[i] = ru[i-1] + ni[i]
    
    q = int(input())
    for i in range(q):
        l, r = map(int,input().split())
        print(ru[r] - ru[l-1])

if __name__ == '__main__':
    f()

Submission status: Accepted

Solution code:
dp = [1]*(10**5+1) #エラトステネスの篩
dp[0],dp[1] = 0, 0
for i in range(2, 10**5+1):
    if dp[i] == 0:
        continue
    j = i
    while j + i <= 10**5:
        j += i
        if dp[j] == 1:
            dp[j] = 0

ni = [0]*(10**5+1) #2012_like check
for i in range(2, 10**5+1):
    if dp[i] == 1 and dp[(i+1)//2] == 1:
        ni[i] = 1

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

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

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 084 D - 2017-like Number
import sys

end_no = 10 ** 5

# 素数判定 エラストテネスの篩
def eratosthenes(N):
    prime = []  # 最後に素数一覧を返す
    data = [i for i in range(2, N + 1)]

    while True:
        p = data[0]

        if p >= N ** 0.5:
            return prime + data

        prime.append(p)
        data = [i for i in data[:] if i % p != 0]


prime = eratosthenes(end_no)
prime = set(prime)

# 累積和の用意
cusum = [0] * (end_no + 1)
for n in range(1, end_no + 1):
    cusum[n] = cusum[n - 1]
    if n % 2 == 0:
        continue

    if n in prime and int((n + 1) / 2) in prime:
        cusum[n] += 1


# 入力
Q = int(input())

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

Submission status: Accepted

Solution code:
dp=[1]*(10**5+1)
dp[0],dp[1]=0,0
for i in range(2,10**5+1):
  if dp[i]==0:
    continue
  j=i
  while j+i<=10**5:
    j+=i
    if dp[j]==1:
      dp[j]-=1
      
ni=[0]*(10**5+1)
for i in range(2,10**5+1):
  if dp[i]==1 and dp[(i+1)//2]==1:
    ni[i]=1

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

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

Submission status: Accepted

Solution code:
n = int(input())

def gen_primes(limit):
    prime_table = [True] * (limit + 1)
    prime_table[0] = False
    prime_table[1] = False
    for i in range(2, int(limit**.5)+1):
        prime_table[i+i::i] = [False] * (limit//i-1)
    return prime_table

primes = gen_primes(10**5)
like2017 = [0] * len(primes)

for i in range(1, len(primes), 2):
    if primes[i] and primes[(i+1)//2]:
        like2017[i] = 1

from itertools import accumulate
like2017 = list(accumulate(like2017))
for _ in range(n):
    l,r = list(map(int, input().split()))
    print(like2017[r] - like2017[l-1])

Submission status: Accepted

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data

primes = set(get_sieve_of_eratosthenes(10**5))
A = []
for i in range(1, 10**5+1):
  if i % 2 == 1:
    if i in primes and (i+1) // 2 in primes:
      A.append(1)
    else:
      A.append(0)
  else:
    A.append(0)

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

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

Submission status: Accepted

Solution code:
from math import ceil, sqrt


def eratosthenes(n):
    hurui = [i for i in range(n + 1)]
    for i in range(2, ceil(sqrt(n)) + 1):
        for j in range(2, ceil(sqrt(i)) + 1):
            if i == 2:
                continue
            if i % j == 0:
                break
        else:
            for k in range(i + i, n, i):
                if hurui[k] != k:
                    continue
                hurui[k] = 0
        continue
    return hurui


n = 10**5 + 200
hurui = eratosthenes(n)
hurui = [bool(i) for i in hurui]
poi = [False] * (n + 1)
for i in range(n + 1):
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i + 1) // 2])
poi[1] = False
sa = [0]
for i in range(n + 1):
    sa.append(sa[i] + poi[i])
q = int(input())
lr = [tuple(map(int, input().split())) for i in range(q)]
for li, ri in lr:
    print(sa[ri + 1] - sa[li])

Submission status: Accepted

Solution code:
from math import ceil, sqrt

n = 10**5+200
hurui = [i for i in range(n+1)]
for i in range(2,ceil(sqrt(n))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,n,i):
            if hurui[k] != k:
                continue
            hurui[k] = 0
    continue

hurui = [bool(i) for i in hurui]
poi = [False]*(n+1)
for i in range(n+1):
    # print(i)
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i+1)//2])
poi[1] = False
#print(poi)
sa = [0]
for i in range(n+1):
    sa.append(sa[i]+poi[i])
#print(sa[:10])

#print(poi[2017])

q = int(input())
lr = [tuple(map(int,input().split())) for i in range(q)]
for li,ri in lr:
    print(sa[ri+1]-sa[li])

Submission status: Accepted

Solution code:
n=7**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
  S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
n=7**6;P=[0,0]+[1]*n;S=[0]*n;r=range(2,n)
for i in r:
  for j in range(2*i,n,i):P[j]=0
for i in r:S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
n=7**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
for i in range(1,n):S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
n=8**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
for i in range(1,n):S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
def isPrime(x):
    ans = True

    for i in range(2, int(x**0.5)+1):
        if x%i == 0:
            ans = False
            break

    return ans

q = int(input())

queries = []
rMax = 1

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

    queries.append((l, r))
    rMax = max(rMax, r)

cnt = [0] * (rMax+1)

for i in range(2, (rMax+1)//2+1):
    cnt[(2*i)-2] = cnt[(2*i)-3]

    if isPrime(i) and isPrime((2*i)-1):
        cnt[(2*i)-1] = cnt[(2*i)-2]+1
    else:
        cnt[(2*i)-1] = cnt[(2*i)-2]

for l, r in queries:
    print(cnt[r] - cnt[l-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]
#############################################################


primes = set(get_sieve_of_eratosthenes(10**5))

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
import sys
sys.setrecursionlimit(10**6)
q = int(input())


def is_prime(n):
    if n <= 1:
        return False

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

    return True


a = []
b = []
c = []
for i in range(0, 10**5+5):
    a_tmp = is_prime(i)

    if i % 2 == 0:
        b_tmp = False
    else:
        b_tmp = is_prime((i+1)//2)

    a.append(a_tmp)
    b.append(b_tmp)
    c.append(a_tmp*b_tmp)

c_sum = [0]
for i in range(1, len(c)):
    c_sum.append(c[i]+c_sum[-1])
# print(c)
# print(c_sum)


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

Submission status: Accepted

Solution code:
import math
Q=int(input())
MAX=10**5
lim=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while lim>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0]!=0]
primes=set(primes+table)

ans=[0]*(MAX+1)
for i in range(3,MAX+1,2):
  if i in primes and (i+1)//2 in primes:
    ans[i]=1
for i in range(1,MAX+1):
  ans[i]=ans[i]+ans[i-1]
for _ in range(Q):
  l,r=map(int,input().split())
  print(ans[r]-ans[l-1])

Submission status: Accepted

Solution code:
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,100000+1):
    for j in range(2,100000//i+1):
        table[i*j]=False
cnt=[0 for _ in range(100000+1)]
for i in range(1,100000+1):
    cnt[i]=cnt[i-1]
    if i%2==1 and table[i]==True and table[(i+1)//2]==True:
        cnt[i]+=1

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

Submission status: Accepted

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


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 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]]
    # x が素数か判定したいとき
    return {2, 3}.union({3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]})


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