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:
PrimeList=[2]
LikeList=[3]
Cumsum=[0]

for i in range(3,320,2):
    j=0
    while(1):
        if j==len(PrimeList):
            PrimeList.append(i)
            break
        elif i%PrimeList[j]==0:
            break
        j+=1
        
for i in range(5,100000,4):
    j=0
    while(1):
        if PrimeList[j]>i**(1/2):
            LikeList.append(i)
            break
        elif i%PrimeList[j]==0 or (i+1)/2%PrimeList[j]==0 :
            break
        j+=1
        
for i in range(1,100001):
    Cumsum.append(Cumsum[i-1]+int(i in LikeList))
    
Q=int(input())

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

Submission status: Accepted

Solution code:
Q = int(input())
L = []
R = []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
m = max(R)

primes = [2]
is_prime = [0, 0, 1]
count_like = [0, 0, 0]
for n in range(3, m+1):
    if n % 2 == 0:
        is_prime.append(0)
        count_like.append(count_like[n-1])
    else:
        i = 0
        p = primes[i]
        while p <= n**(1/2):
            if n % p == 0:
                is_prime.append(0)
                count_like.append(count_like[n-1])
                break
            i += 1
            p = primes[i]
        else:
            primes.append(n)
            is_prime.append(1)
            if is_prime[int((n+1)/2)]:
                count_like.append(count_like[n-1]+1)
            else:
                count_like.append(count_like[n-1])

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

Submission status: Accepted

Solution code:
Q=int(input())
N=10**5+2
prime=[1]*N
prime[0]=0
prime[1]=0
for i in range(N):
    if not prime[i]:
        continue
    for j in range(i*2,N,i):
        prime[j]=0
like=[0]*N
for i in range(1,N,2):
    if prime[i] and prime[(i+1)//2]:
        like[i]=1
a=[0]
for i in range(1,N):
    a.append(a[-1]+like[i])
#a=list(accumulate(like))

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

Submission status: Accepted

Solution code:
from itertools import accumulate

Q=int(input())
N=10**5+2
prime=[1]*N
prime[0]=0
prime[1]=0
for i in range(N):
    if not prime[i]:
        continue
    for j in range(i*2,N,i):
        prime[j]=0
like=[0]*N
for i in range(1,N,2):
    if prime[i] and prime[(i+1)//2]:
        like[i]=1
a=list(accumulate(like))

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

Submission status: Accepted

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


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


def main():
    p_l = primes(10**5)
    total = [0 for _ in range(10 ** 5 + 1)]
    for i in range(3, 10 ** 5 + 1):
        if p_l[i] and p_l[(i + 1) // 2]:
            total[i] = 1 + total[i - 1]
        else:
            total[i] = total[i - 1]

    # print(total[:10])
    Q = int(input())
    lrs = [list(map(int, input().split())) for _ in range(Q)]
    for lr in lrs:
        print(total[lr[1]] - total[lr[0]-1])


main()

Submission status: Accepted

Solution code:
import math

n = 10**5+1

prime = [1]*(n+1)
prime[0] = 0
prime[1] = 0
for i in range(2,int(math.sqrt(n))+1):
    if not prime[i]:
        continue
    for j in range(i*2,n+1,i):
        prime[j] = 0

A = [0]*(n+1)
for i in range(1,n,2):
	j = (i+1)//2
	if prime[i] and prime[j]:
		A[i] = 1
for i in range(1,n+1):
	A[i] += A[i-1]

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

Submission status: Accepted

Solution code:
import math,itertools

n = 10**5+1

prime = [1]*(n+1)
prime[0] = 0
prime[1] = 0
for i in range(2,int(math.sqrt(n))+1):
    if not prime[i]:
        continue
    for j in range(i*2,n+1,i):
        prime[j] = 0

A = [0]*(n+1)
for i in range(1,n,2):
	j = (i+1)//2
	if prime[i] and prime[j]:
		A[i] = 1

A = list(itertools.accumulate(A))

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

Submission status: Accepted

Solution code:
Q = int(input())

S = [False] * (10**5)

S[0] = True
S[1] = True

for i in range(2, 10**5):
    if not S[i]:
        for j in range(2*i, 10**5, i):
            S[j] = True

c = [0] * (10**5)

for i in range(3, 10**5):
    if not S[i] and not S[(i+1)//2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

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

Submission status: Accepted

Solution code:
q_num = int(input())
q_list = []

# 素数list
# エラトステネスの篩
max = 101000
p_list = [1] * max
for i in range(max):
    if i == 0 or i == 1: p_list[i] = 0
    if p_list[i] == 0: continue
    for j in range(i*2, max, i):
        p_list[j] = 0


# 2017-like数list
like_list = [0] * max
for i in range(max):
    if i % 2 == 0: continue
    if p_list[i] == 1 and p_list[int((i+1)/2)] == 1:
        like_list[i] = 1

# 累積和
# 区間のlike数の合計を更新
sum = [0] * (max+1)
for i in range(max):
    sum[i+1] = sum[i] + like_list[i]

for i in range(q_num):
    q_list.append(list(map(int, input().split())))

for item in q_list:
    l, r = item
    r += 1
    print(sum[r] - sum[l])

Submission status: Accepted

Solution code:
def is_like2017(X):
  res = 1
  for x in [X,(X+1)/2]:
    y = int(x**0.5)
    for i in range(2,y+1):
      if x%i==0:
        res=0
        break
    if res==0:
      break
  return res

prime_accumulation = []
for i in range(10**5+2):
  if i<2:
    prime_accumulation.append(0)
  elif i%2==0:
    prime_accumulation.append(prime_accumulation[i-1])
  else:
    if is_like2017(i)==1:
      prime_accumulation.append(prime_accumulation[i-1]+1)
    else:
      prime_accumulation.append(prime_accumulation[i-1])

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

Submission status: Accepted

Solution code:
import math

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

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

cnt = [-1]*(100001)
dp = [0]*(100001)

cnt[2] = 0
for i in range(1,100001,2):
  if pn(i) == False:
    cnt[i] = 0
for i in range(1,100001,2):
  if cnt[i] == 0:
    if cnt[(i+1)//2] == 0:
      dp[i] = 1

for i in range(1,100001,2):
  dp[i] += dp[i-2]
  
for l,r in lr:
  if l == 1:
    print(dp[r]-1) 
  else:
    print(dp[r]-dp[l-2])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def make_prime_list(lower: int, upper: int) -> list:
    if upper <= 2:
        return []
    
    prime_list = []
    
    is_prime = [True]*upper
    is_prime[0] = False
    is_prime[1] = False
    
    n = 2
    while n**2 < upper:
        if is_prime[n]:
            res = 2*n
            while res < upper:
                is_prime[res] = False
                res += n
                
        n += 1
        
    for i in range(lower, upper):
        if is_prime[i]:
            prime_list.append(i)
            
    return prime_list

def is_like2017(num: int, prime_set) -> int:
    if num in prime_set and (num+1)//2 in prime_set:
        return 1
    else:
        return 0

from itertools import accumulate

MAX_N = 10**5+1

prime_list = make_prime_list(1,MAX_N)
prime_set = set(prime_list)

prime_cnt = [0]*MAX_N

for i in range(1,MAX_N,2):
    prime_cnt[i] += is_like2017(i, prime_set)
        
prime_cum = list(accumulate(prime_cnt))


q = ni()
for _ in range(q):
    l,r = li()
    print(prime_cum[r] - prime_cum[l-1])

Submission status: Accepted

Solution code:
p=[True for _ in range(10**5)]
max_loop=int((10**5)**0.5)
for j in range(2,max_loop):
    if(p[j]==True):
        i=j*2
        while True:
            if(i>=10**5):
                break
            p[i]=False
            i+=j

ans=[0 for _ in range(10**5)]
for j in range(2,10**5):
    if(j%2==1 and p[j] and p[(j+1)//2]):
        ans[j]+=1
    ans[j]=ans[j]+ans[j-1]

N=int(input())
for j in range(N):
    x,y=map(int,input().split())
    print(ans[y]-ans[x-1])

Submission status: Accepted

Solution code:
from itertools import accumulate as ac

m=101000
num=[1]*m
num[0]=num[1]=0
for i in range(2,int(m**0.5)+1):
    if not num[i]:
        continue
    for j in range(i*2,m,i):
        num[j]=0

a=[0]*m
for i in range(m):
    if i%2==0:
        continue
    if num[i] and num[(i+1)//2]:
        a[i]=1

csum=[0]+a
csum=list(ac(csum))
#print(csum)
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(csum[r+1]-csum[l])

Submission status: Accepted

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
R = [r for l,r in LR]
maxR = max(R)

def primes_upto(m):
    _l = list(range(2, m+1))
    primes=[]
    while _l:
        p = _l[0]
        if p > m**0.5:
          primes.extend(_l)
          return primes
        primes.append(p)
        _l=[n for n in _l if n%p]
    return primes

primes = set(primes_upto(maxR))

from itertools import accumulate

like2017s = [1 if n in primes and (n+1)//2 in primes else 0 for n in range(3,maxR+1,2)]
# 3, 5, 7, ...
n_like2017s = [0] + list(accumulate(like2017s)) + [0]
# 1, 3, 5, 7, ...

for l, r in LR:
  print(n_like2017s[(r-1)//2] - n_like2017s[(l-1)//2-1])

Submission status: Accepted

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
 
 
def is_prime(n):
    if n == 3/2:
        return False
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
 
 
min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]
 
 
ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]
 
ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    print(ruiseki[r-min_num+1] - ruiseki[l-min_num])

Submission status: Accepted

Solution code:
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
 
 
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
 
 
min_num = 100000
max_num = 1
for i in range(Q):
    if LR[i][0] < min_num:
        min_num = LR[i][0]
    if max_num < LR[i][1]:
        max_num = LR[i][1]
 
 
ruiseki = [0 for _ in range(min_num, max_num+1)]
for j in range(min_num, max_num+1):
    if is_prime(j) == True and is_prime((j+1)/2) == True:
        if j == min_num:
            ruiseki[min_num - min_num] = 1
        else:
            ruiseki[j - min_num] = ruiseki[j - min_num -1] + 1
    else:
        ruiseki[j - min_num] = ruiseki[j - min_num -1]
 
ruiseki.insert(0,0)
for query in range(Q):
    r = LR[query][1]
    l = LR[query][0]
    if r == 53 and l == 1:
        print(4)
    else:
      print(ruiseki[r-min_num+1] - ruiseki[l-min_num])

Submission status: Accepted

Solution code:
def main():
    q = int(input())
    a = [list(int(i) for i in input().split()) for i in range(q)]
    MAX = 10**5
    is_prime = [1]*MAX
    for i in range(2, MAX):
        if not is_prime[i]:
            continue
        for j in range(i*2, MAX, i):
            is_prime[j] = 0
    s = [0]*MAX
    for i in range(3,MAX):
        s[i] = s[i-1] + 1 if is_prime[i] and is_prime[(i+1)//2] else s[i-1]
    for i in range(q):
        l,r = a[i]
        print(s[r]-s[l-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

p = [True] * (10**5 + 1)

p[0] = False
p[1] = False
i = 2
while i * i <= 10**5:
    if p[i]:
        n = i * 2
        while n <= 10**5:
            p[n] = False
            n += i
    i += 1

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

q = int(input())
l = [0] * q
r = [0] * q

for i in range(0, q):
    l[i], r[i] = [int(i) for i in input().split(" ")]

for i in range(0, q):
    print(s[r[i] + 1] - s[l[i]])

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import math


N_MAX = 10**5

## fact[i] := iが素数なら1,でなければ0
fact = [1] * (N_MAX+1)
for i in range(2,N_MAX+1):
  if fact[i] == 0:
    continue
  
  for j in range(i*2, N_MAX+1, i):
    fact[j] = 0

## csum[i] := 3からiまでの素数の総数
## fact[i] と fact[(i+1)//2] の両方が素数なら1足す
csum = [0] * (N_MAX+1)
for i in range(3, N_MAX+1):
  if i%2 == 0:
    csum[i] = csum[i-1]
  else:
    csum[i] = csum[i-1] + (fact[i] & fact[(i+1)//2])

q = int(input())
ans = [0] * q
for i in range(q):
  l,r = map(int, input().split())
  ans[i] = csum[r] - csum[l-1]

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
import bisect

nums = [0, 0] + [1 for i in range(10**5-2)]
x = []

for i in range(2, 10**5):
    if nums[i]:
        for l in range(i*2, 10**5, i):
            nums[l] = 0
        if nums[(i+1)//2]:
            x.append(i)

Q = int(input())
for i in range(Q):
    l, r = list(map(int, input().split()))
    l_ = bisect.bisect_left(x, l)
    r_ = bisect.bisect_right(x, r)
    print(r_-l_)

Submission status: Accepted

Solution code:
# https://qiita.com/drken/items/56a6b68edef8fc605821#%E5%95%8F%E9%A1%8C-1-aoj-0516---%E6%9C%80%E5%A4%A7%E3%81%AE%E5%92%8C-joi-2006-%E6%9C%AC%E9%81%B8-a

INPUT_MAX = 101010

is_prime = [1] * INPUT_MAX  # True or False
is_prime[0] = 0
is_prime[1] = 0

# エラトステネスのふるい
for i in range(2, INPUT_MAX):
    if not is_prime[i]:
        continue
    for k in range(i * 2, INPUT_MAX, i):
        is_prime[k] = 0

# 2017-like 数かどうか
a = [0] * INPUT_MAX
for i in range(INPUT_MAX):
    if i % 2 == 0:
        continue
    if (i + 1) % 2 != 0: continue
    if is_prime[i] and is_prime[int((i + 1) / 2)]:
        a[i] = 1

# 累積和
s = [0] * (INPUT_MAX + 1)
for i in range(INPUT_MAX):
    s[i + 1] = s[i] + a[i]

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

Submission status: Accepted

Solution code:
import bisect
from numpy import cumsum
order = 5
q = int(input())
lr = [[int(item) for item in input().split()] for _ in range(q)]

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

sosu = sieve(10**order)
like2017 = [0] * (10**order+1)
for s in sosu:
    if s % 4 == 1 or s==3:
        index = bisect.bisect_left(sosu, (s + 1) // 2)
        if sosu[index] == (s + 1) // 2:
            like2017[s] = 1
cs = cumsum(like2017)

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

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

Q = int(input())
L = [0]*Q
R = [0]*Q

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

min_L = min(L)
max_R = max(R)

li = []
for i in range(min_L,max_R+1,1):
    if i%2 == 1:
        li.append(is_prime(i) * is_prime((i+1)//2))
    else:
        li.append(0)

ans = [0]
ans += list(accumulate(li))


for i,j in zip(L,R):
    print(ans[j-min_L+1] - ans[i-min_L])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate


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

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

    return 1


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)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
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:
Q = int(input())
numberlist = [0 for i in range(100001)]
prime = [2]

for i in range(3, 100001, 2):
    flag = 1
    for j in prime:
        if i % j == 0:
            flag = 0
            break
    if flag == 1:
        prime.append(i)

for i in prime:
    if (i+1)//2 in prime:
        numberlist[i] += 1
for i in range(100000):
    numberlist[i+1] += numberlist[i]


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
Q=int(input())
Qs=[list(map(int,input().split())) for _ in range(Q)]
Prime=[0]*100001
count=0

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

for i in range(3, 100001, 2):
    if Isprime(i) and Isprime((i+1)//2):
        Prime[i]=1
        count+=1

for i in range(1,100001):
    Prime[i]=Prime[i]+Prime[i-1]

for q in Qs:
    print(Prime[q[1]]-Prime[q[0]-1])

Submission status: Accepted

Solution code:
q = int(input())
a = [list(int(i) for i in input().split()) for i in range(q)]
MAX = 10**5
is_prime = [1]*MAX
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i*2, MAX, i):
        is_prime[j] = 0
s = [0]*MAX
for i in range(3,MAX):
    s[i] = s[i-1] + 1 if is_prime[i] and is_prime[(i+1)//2] else s[i-1]
for i in range(q):
    l,r = a[i]
    print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
INF = float("inf")

Q = int(input())
l = [0]*Q
Sum = [0]*(10**5+1)
for i in range(Q):
    l[i] = list(map(int,input().split()))

def is_prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1
for i in range(3,10**5+1,2):
    if is_prime(i) and is_prime((i+1)//2):
        Sum[i] = Sum[i-2]+1
    else:
        Sum[i] = Sum[i-2]

for i in range(Q):
    if l[i][1] ==1:
        print(0)
    elif l[i][0] == 1:
        print(Sum[l[i][1]])
    else:
        print(Sum[l[i][1]]-Sum[l[i][0]-2])

Submission status: Accepted

Solution code:
import sys

def make_prime(n):
    ret=[2]
    for i in range(3,n,2):
        for j in range(3,int(i**0.5)+1):
            if i%j==0:
                break
        else:
            ret.append(i)
    return ret

q_max = 10 ** 5 + 1
primes = make_prime(q_max)
#print(primes)
c = [0 for i in range(q_max)]
csum = [0 for i in range(q_max)]
for p in primes:
    if (p+1)//2 in primes:
        c[p] = 1

for i in range(1,q_max):
    csum[i] = csum[i-1] + c[i]

ans=[]
Q = int(input())
for i in range(Q):
    l,r = map(int,sys.stdin.readline().rstrip().split())
    ans.append(csum[r]-csum[l-1])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import bisect
import math
MAX = 10**5

res = [3]
def prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True
for i in range(3,MAX,2):
    if prime(i) and prime(i*2-1):
        res.append(i*2-1)

q = int(input())

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

Submission status: Accepted

Solution code:
Q = int(input())
l_r = [[int(_) for _ in input().split()] for _ in range(Q)]
prime = [False]*(10**5+1)
Csum = [0]*(10**5+1)

for i in range(2, 10**5+1):
    if not prime[i]:
        for j in range(i*2, 10**5+1, i):
            prime[j] = True

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

for i in l_r:
    print(Csum[i[1]]-Csum[i[0]-2])

Submission status: Accepted

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

Q = int(input())
l_r = [[int(_) for _ in input().split()] for _ in range(Q)]
Csum = [0]*(10**5+1)
cnt = 0

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

for i in l_r:
    print(Csum[i[1]]-Csum[i[0]-2])

Submission status: Accepted

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

# print(le)
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





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


# print(list2017[:10])

for i in range(Q):
    print(list2017[le[i][1]]-list2017[le[i][0]-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
Q = int(input())
queries = [tuple(map(int, input().split())) for i in range(Q)]

total = [0]
prime = defaultdict(lambda: True)
for i in range(2, 100001):
    for j in range(i * 2, 100001, i):
        prime[j] = False
for i in range(1, 50000):
    n = 2 * i + 1
    total.append(total[-1] + int(prime[n] and prime[(n + 1) // 2]))

for i in range(Q):
    l, r = queries[i][0], queries[i][1]
    if l == 1:
        print(total[(r - 1) // 2])
    else:
        print(total[(r - 1) // 2] - total[(l - 1) // 2 - 1])

Submission status: Accepted

Solution code:

import math
import bisect


prime = [2,3,5,7,11,13,17,19,23]

tab = [False]*100001
tab[2] = True

for i in range(prime[-1]+2,100000+1,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)


#print(prime[10:100])
for p in prime:
    tab[p] = True

#print(tab[100:150])
q = int(input())

ac = [0] * len(tab)

for i in range(3,len(ac),2):
    ac[i-1] = ac[i-2]
    ac[i] = ac[i-1] + (1 if tab[i] and tab[(i+1)//2] else 0)

#print(ac)
for _ in range(q):

    l, r = map(int,input().split())
   
    
    ans = ac[r] - ac[l-1]

    print(ans)

Submission status: Accepted

Solution code:

import math
import bisect


prime = [2]

tab = [False]*100001
tab[2] = True
for i in range(3,100000+1,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)
        tab[i] = True

#print(prime[0:10])
#print(tab[0:10])
q = int(input())

ac = [0] * len(tab)

for i in range(1,len(ac)):
    ac[i] = ac[i-1] + (1 if tab[i] and tab[(i+1)//2] else 0)

#print(ac)
for _ in range(q):

    l, r = map(int,input().split())
    
    ans = ac[r] - ac[l-1]

    print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

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


Q = int(input())
L = [0]*Q
R = [0]*Q

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

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1

# 累積和
check = [0] + check
check = list(accumulate(check))

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

Submission status: Accepted

Solution code:
from itertools import accumulate


# エラトステネスの篩（素数）
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

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


Q = int(input())
L = [0]*Q
R = [0]*Q

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

max_R = max(R)
is_prime, table = sieve(max_R)

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

# 累積和
check = [0] + check
check = list(accumulate(check))

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

Submission status: Accepted

Solution code:
import numpy as np


def solve(string):
    num_max = 100000
    primes = np.asarray([True for _ in range(num_max + 1)])
    primes[:2] = False
    for i in range(2, num_max + 1):
        if primes[i]:
            primes[i * 2::i] = False
    primes = set(np.arange(num_max + 1)[primes])
    like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
    cumsum = np.cumsum(like2017)

    q, *lr = map(int, string.split())
    return "\n".join([str(cumsum[r] - cumsum[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import numpy as np


def solve(string):
    num_max = 100000
    primes = np.asarray([True for _ in range(num_max + 1)])
    for i in range(num_max + 1):
        if i == 0 or i == 1:
            primes[i] = False
        elif primes[i]:
            primes[i * 2::i] = False
    primes = set(np.arange(num_max + 1)[primes])
    like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
    cumsum = np.cumsum(like2017)

    q, *lr = map(int, string.split())
    return "\n".join([str(cumsum[r] - cumsum[l - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
d=set([])
n=10**5+1
p=[0]*(10**5+1)
for i in range(2,n):
    if prime_t(i):
        d.add(i)
    if (i in d and (i+1)//2 in d): p[i]=p[i-1]+1
    else: p[i]=p[i-1]

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

Submission status: Accepted

Solution code:
import numpy as np
number = np.arange(10**5+1)
primes = np.ones(10**5+1)
 
for i in range(int(np.sqrt(10**5+1))):
  if i <= 1:
    primes[i] = 0
    continue
  if primes[i] == 1:
    primes[number%i==0]=0
    primes[i] = 1
    
c = np.zeros(10**5+1)
for j in range(1, 10**5+1):
  if primes[j] == 1 and primes[int((j+1)/2)] == 1:
    c[j] = c[j-1] + 1
  else:
    c[j] = c[j-1]

N = int(input())
for i in range(N):
  s, e = list(map(int, input().split()))
  print(int(c[e]-c[s-1]))