Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

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

q=int(input())
f=[1]*(10**5+1)
f[0],f[1]=0,0
n=len(f)
for i in range(2,n):
  if isPrime(i):
    for j in range(i*2,n,i):
      f[j]=0

c=[0]*(10**5+1)
for i in range(2,10**5+1):
  if i%2==1:
    if f[i]==1 and f[(i+1)//2]==1:
      c[i]=c[i-1]+1
      continue
    c[i]=c[i-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:
def resolve():
    q = int(input())
    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
    prime = []
    prime2 = []
    for i in range(1, 10**5):
        if is_prime(i):
            prime.append(i)
    primes = set(prime)
    for i in range(0, len(prime)):
        if (((prime[i])+1)//2) in primes:
            prime2.append(prime[i])
    prime2s = set(prime2)
    ans = [0]*(10**5+1)
    count = 0
    for i in range(0, 10**5+1):
        if i in prime2s:
            count += 1
        ans[i] = count
    for i in range(q):
        l, r = map(int, input().split())
        print(ans[r+1]-ans[l-1])
resolve()

Submission status: Accepted

Solution code:
from math import ceil

# def prime(n):
#     prime_list = [2]
#     for i in range(3, n, 2):
#         cnt = 0
#         for j in range(2, int(i**(0.5))-1):
#             if i % j == 0:
#                 cnt += 1
#             # if j == int(i ** (0.5)):
#             #     continue
#         if cnt == 0:
#             prime_list.append(i)
#
#     return prime_list
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 [i for i in range(n + 1) if is_prime[i]]

p_list = primes(10**5)
p_set = set(p_list)
cnt = 0
a = [0] * 10**5
for i in range(10**5):
    if i in p_set:
        if ceil(i/2) in p_set:
            cnt += 1
            # print(i)
    a[i] = cnt
# print(p_list)
# print(a)

q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    print(a[c] - a[b-1])

Submission status: Accepted

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


def primes(n):
    ret = []
    A = [i for i in range(2, n+1)]
    k = 0
    s = n**0.5
    while(k < s):
        ret.append(A[0])
        k = A[0]
        A = [x for x in A if x % k]
    ret += A
    return ret


prime = primes(10**5)

prime_s = set(prime)
t = [0]*(10**5 + 1)
for i in range(1, 10**5+1):
    if i in prime_s and (i+1)//2 in prime_s:
        t[i] = 1
for i in range(1, 10**5+1):
    t[i] = t[i] + t[i-1]

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

Submission status: Accepted

Solution code:
Q=int(input())
A=[0]
S=[0]*(10**5+1)
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

def id2017(n):
  if is_prime(n) and is_prime((n+1)/2):
    return True
  else:
    False
count=0    
for i in range(1,10**5+1):
  if id2017(i) and i%2==1:
    count+=1
  S[i]=count
for i in range(Q):
  l,r=map(int, input().split())
  print(S[r]-S[l-1])

Submission status: Accepted

Solution code:

Q = int(input())
N = 10**5 + 1000

def getPrimes():
    isPrime = [True] * N
    isPrime[1] = False
    for i in range(2, N):
        if not isPrime[i]:
            continue
        for p in range(i + i, N, i):
            isPrime[p] = False
    return isPrime

isPrime = getPrimes()

A = [0] * (N)
for i in range(2, N):
    if i % 2 == 1 and isPrime[i] and isPrime[(i + 1) // 2]:
        A[i] = 1
accA = [0] * (N + 1)
for i, a in enumerate(A, start=0):
    accA[i] += accA[i - 1] + a

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

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate

    def Eratosthenes(x: int) -> set:
        from math import sqrt
        sup = int(x)
        primes = {i for i in range(2, sup+1)}
        for i in range(2, int(sqrt(sup+1))+1):
            if i in primes:
                mul = 2
                while i*mul <= sup:
                    primes.discard(i*mul)
                    mul += 1
        return primes
    P = Eratosthenes(10**5+5)
    A = [0]*(10**5+5)
    for i in range(3, 10**5+5):
        if i in P and (i+1)//2 in P:
            A[i] += 1
    S = list(accumulate(A))

    Q = int(input())
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    for le, ri in LR:
        print(S[ri] - S[le-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a=set(primes(100100))
b=[0]
for i in range(100100):
    f=0
    if i%2==1 and i in a and (i+1)//2 in a:
        f=1
    b.append(b[-1]+f)
q=int(input())
for i in range(q):
    a=list(map(int,input().split()))
    print(b[a[1]+1]-b[a[0]])

Submission status: Accepted

Solution code:
import bisect
def prime(n):
    max_=int(n**0.5)
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max_:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes
Q=int(input())
arr=prime(100000)
likenum=[]
n=len(arr)
for i in range(n):
    lik=(arr[i]+1)//2
    x=bisect.bisect_left(arr,lik)
    if(x<n and arr[x]==(lik)):
        likenum.append(arr[i])
for i in range(Q):
    L,R=map(int,input().split())
    r=bisect.bisect_left(likenum,R)
    l=bisect.bisect_left(likenum,L)
    if(r<len(likenum) and likenum[r]==R):
        r+=1
    print(r-l)

Submission status: Accepted

Solution code:
q = int(input())
lr = [list(map(int,input().split()))for _ in range(q)]
maxr = 0
for i in range(q):
    maxr = max(maxr,lr[i][1])
res = 0
cnt = [0]*(maxr+3)
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 [i for i in range(n + 1) if is_prime[i]]
x = primes(maxr+1)
for i in range(1,maxr+1):
    if i%2 == 0:
        cnt[i] = res
        continue
    if i in x and (i+1)//2 in x:
        res+=1

    cnt[i] = res
for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    print(cnt[r]-cnt[l-1])

Submission status: Accepted

Solution code:
Q=int(input())

fact=[True]*(10**5+1)
fact[0]=False
fact[1]=False

num=[0]*(10**5+1)
cur=0
for i in range(len(fact)):
  if fact[i]:
    for j in range(i*2,len(fact),i):
      fact[j]=False
    if fact[(i+1)//2]:
      cur+=1
  num[i]=cur
      
for i in range(Q):
  l,r=map(int,input().split())
  print(num[r]-num[l-1])

Submission status: Accepted

Solution code:
def is_prime(n):
    result = True
    i = 2
    while i * i <= n:
        if n % i == 0:
            result = False
            break
        i += 1
    if n == 1:
        result = False
    return result


def main():
    q = int(input())
    max_num = 10 ** 5
    count_num = [0 for _ in range(max_num + 1)]
    is_prime_num = [False for _ in range(max_num + 1)]
    count_num[3] = 1
    is_prime_num[3] = True
    for i in range(4, max_num + 1):
        count_num[i] = count_num[i - 1]
        if i % 2:
            if is_prime(i):
                is_prime_num[i] = True
                count_num[i] = count_num[i - 1]
                if is_prime_num[(i + 1) // 2]:
                    count_num[i] += 1
    for _ in range(q):
        l, r = map(int, input().split())
        print(count_num[r] - count_num[l - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

NN = 10 ** 5 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
primescnt = [0 for _ in range(NN + 1)]
for i in range(3, NN + 1):
    primescnt[i] = primescnt[i - 1] + int(isprime[i] and isprime[(i + 1) // 2])
q = INT()
for _ in range(q):
    l, r = MAP()
    print(primescnt[r] - primescnt[l - 1])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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
n = 10**5+10
Q = inp()
ch = [False] * (n+5)
for i in range(1,n):
    if is_prime(i):
        ch[i] = True
table = [0] * (n+5)
for i in range(1,n):
    tmp = 0
    if i%2 and ch[i] and ch[(i+1)//2]:
        tmp = 1
    table[i] = table[i-1] + tmp
for _ in range(Q):
    a,b = inpl()
    print(table[b] - table[a-1])

Submission status: Accepted

Solution code:
q = int(input())

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):
        # 既にfalseになってたらスキップ
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return is_prime
prime_ls = primes(10**5)

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

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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 = inp()
cnt = [False] * (10**5+10)
table = [False] * (10**5+10)
for i in range(1,10**5+5):
    cnt[i] = is_prime(i)
for i in range(1,10**5+5):
    table[i] = i%2 and cnt[i] and cnt[(i+1)//2]
res = [0] * (10**5+5)
for i in range(10**5+4):
    tmp = 1 if table[i] else 0
    res[i+1] = res[i] + tmp
# print(res[:20])
for _ in range(Q):
    a,b = inpl()
    print(res[b+1] - res[a])

Submission status: Accepted

Solution code:
import math


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

q = int(input())
csum = [0, ]

i = 0
for m in range(1, 100000-1+1, 2):
    if prime_judge(m) and prime_judge(int((m+1)/2)):
        csum.append((csum[i]+1))
    else:
        csum.append(csum[i])
    i += 1

ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(csum[int(r/2)+1] - csum[int(l/2)])

for i in ans:
    print(i)

Submission status: Accepted

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

def main():
    def is_prime(n):
        if n == 1: return False
        for k in range(2, int(n**(1/2)) + 1):
            if n % k == 0:
                return False
        return True
    
    prime,now = [0],0
    for i in range(1,10**5+1):
        if i%2 == 1 and is_prime(i) and is_prime((i+1)//2):
            now += 1
        prime.append(now)
    
    N = int(input())
    for _ in range(N):
        a,b = map(int,input().split())
        print(prime[b]-prime[a-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


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

    # 素数のlist
    prime_list = set(primes(10 ** 5 + 1)) # setにしないと、ものすごい遅い

    """
    # 10^5 * 10 ^ 5なので✗
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    cum_2017 = [0, 0]
    # 累積和的に、2017に似た数カウントをする
    tmp = 0
    for i in range(2, 10 ** 5 + 1, 1):
        if i in prime_list and (i + 1) / 2 in prime_list: # (i + 1) // 2 でなく、(i + 1) / 2にすると遅い
            tmp += 1
            cum_2017.append(tmp)
        else:
            cum_2017.append(tmp)

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



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


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

    # 素数のlist
    prime_list = primes(10 ** 5 + 1) # setにしないと、ものすごい遅い

    """
    # 10^5 * 10 ^ 5なので✗
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    cum_2017 = [0, 0]
    # 累積和的に、2017に似た数カウントをする
    tmp = 0
    for i in range(2, 10 ** 5 + 1, 1):
        if i in prime_list and (i + 1) // 2 in prime_list: # (i + 1) // 2 でなく、(i + 1) / 2にすると遅い
            tmp += 1
            cum_2017.append(tmp)
        else:
            cum_2017.append(tmp)

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



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


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

    # 素数のlist
    prime_list = set(primes(10 ** 5 + 1)) # setにしないと、ものすごい遅い

    """
    # 10^5 * 10 ^ 5なので✗
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    cum_2017 = [0, 0]
    # 累積和的に、2017に似た数カウントをする
    tmp = 0
    for i in range(2, 10 ** 5 + 1, 1):
        if i in prime_list and (i + 1) // 2 in prime_list: # (i + 1) // 2 でなく、(i + 1) / 2にすると遅い
            tmp += 1
            cum_2017.append(tmp)
        else:
            cum_2017.append(tmp)

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



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import itertools


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 (i for i in range(n + 1) if is_prime[i])


P = set(primes(10 ** 5))
L = [0] * 10 ** 5
for i in range(1, 10 ** 5, 2):
    if i in P and (i + 1) // 2 in P:
        L[(i + 1) // 2] = 1

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

Submission status: Accepted

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

is_prime = [1 for i in range(n+1)]
is_prime[0], is_prime[1] = 0, 0

#エラトステネスの篩
for i in range(2, n+1):
    if (not is_prime[i]):
        continue
    for j in range(i*2, n+1, i):
        is_prime[j] = 0

for i in range(2, n+1):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[int((i+1)/2)]:
        a[i] = 1

s = [0 for i in range(n+1)]
for i in range(n):
    s[i+1] = s[i] + a[i]

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

Submission status: Accepted

Solution code:
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

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

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

primes = sieve(10 ** 5)
likes = [primes[n] & primes[(n + 1) // 2] if n %  2 != 0 else False
         for n in range(10 ** 5)]
cumsum = [0] * (10 ** 5 + 1)
for i in range(10 ** 5):
    cumsum[i + 1] = cumsum[i] + int(likes[i])

for l, r in X:
    print(cumsum[r + 1] - cumsum[l])

Submission status: Accepted

Solution code:
import math
import itertools
import bisect
import sys
input = sys.stdin.readline


# 素数判定
def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0
    prime=[]

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = 2 * i
            while j <= n:
                is_prime[j - 1] = 0
                j += i
    for i in range(n):
        if is_prime[i]==1:
            prime.append(i+1)
    return prime


# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(pow(10,5))
ans=[]
for i in range(len(v)):
    x=(v[i]+1)//2
    index = bisect.bisect_left(v, x)
    if v[index]==x:
        ans.append(v[i])

for i,j in s:
    r = bisect.bisect_left(ans, j+1)
    l = bisect.bisect_left(ans, i-1)
    print(r-l)

Submission status: Accepted

Solution code:
def Prime_number(x):
    # xは2以上の自然数
    # 素数:True
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

like_number=[0 for _ in range(10**5+1)]
cnt=0
for i in range(2,10**5+1):
    if i%2==0:
        continue
    if Prime_number(i) and Prime_number((i+1)//2):
        cnt+=1
    like_number[i]=cnt

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

Submission status: Accepted

Solution code:
Q = int(input())
lll = []
rrr = []
for i in range(Q):
    buff = [int(i) for i in input().split()]
    lll.append(buff[0])
    rrr.append(buff[1])

def get_sieve_of_eratosthenes(n):#遅い?改善の余地あり。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]
    return(data)

Nmax = 10**5+5
#Nmax=10

isprime = [0 for i in range(Nmax)]
for i in get_sieve_of_eratosthenes(Nmax):
    isprime[i] = 1

cumulative_sum = [0 for i in range(Nmax)]
for i in range(1,Nmax):
    if i%2==1 and isprime[i]==1 and isprime[(i+1)//2]==1:
        cumulative_sum[i] = cumulative_sum[i-1]+1
    else:
        cumulative_sum[i] = cumulative_sum[i-1]

#print(cumulative_sum)

for l,r in zip(lll,rrr):
    #print(l,r)
    print(cumulative_sum[r]-cumulative_sum[l-1])

Submission status: Accepted

Solution code:
q = int(input())
def prime(n):
    if any(n%i==0 or ((n+1)/2)%i==0 for i in range(2,int(n**(1/2))+1)):
        return False
    else:
        return True
cum = [0]*(10**5)
cum[3]=1
for i in range(4,10**5):
    cum[i]=cum[i-1]
    if prime(i):
        cum[i]+=1
for i in range(q):
    l,r = map(int,input().split())
    print(cum[r]-cum[l-1])

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

MAX = 100010
ps = [True] * MAX
ps[0] = ps[1] = False

def prime():
    for i in range(2, MAX):
        if ps[i]:
            j = 2 * i
            while j < MAX:
                ps[j] = False
                j += i

cs = [0] * MAX
def cnt():
    for i in range(1, MAX):
        if i % 2 == 1 and ps[i] and ps[(i + 1) // 2]:
            cs[i] = cs[i - 1] + 1
        else:
            cs[i] = cs[i - 1]

prime()
cnt()

Q = int(input())

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

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc084/tasks/abc084_d
# 18:49-19:10 中断
# 0:21-1:10 done


def prime_set(limit=10**5):
    ret = [2]
    for x in range(3, limit+1, 2):
        is_prime = True
        sqrtx = int(pow(x, 0.5))

        for p in ret:
            if p > sqrtx:
                break

            if x % p == 0:
                is_prime = False
                break

        if is_prime:
            ret.append(x)

    return ret


def bin_search(xs, start, end, x):
    idx = start + (end-start) // 2
    if x < xs[idx]:
        return bin_search(xs, start, idx, x)
    elif x > xs[idx]:
        return bin_search(xs, idx+1, end, x)
    else:
        return idx


def geq_search(xs, start, end, x):
    if end - start < 2:
        if x <= xs[start]:
            return start
        else:
            return start+1

    idx = start + (end-start) // 2

    if x <= xs[start]:
        return start
    elif xs[idx-1] < x <= xs[idx]:
        return idx

    if x < xs[idx]:
        return geq_search(xs, start, idx+1, x)
    elif x > xs[idx]:
        return geq_search(xs, idx, end, x)
    else:
        return idx


def leq_search(xs, start, end, x):
    if end - start < 2:
        if x >= xs[start+1]:
            return start+1
        else:
            return start

    idx = start + (end-start) // 2

    if x >= xs[end-1]:
        return end-1
    elif xs[idx-1] <= x < xs[idx]:
        return idx-1

    if x < xs[idx]:
        return leq_search(xs, start, idx+1, x)
    elif x > xs[idx]:
        return leq_search(xs, idx, end, x)
    else:
        return idx


def main():
    # primes = prime_set(100)
    # print(primes)
    # print(len(primes))
    # print(leq_search(primes, 0, len(primes), 2))
    # print(leq_search(primes, 0, len(primes), 3))
    # print(leq_search(primes, 0, len(primes), 96))
    # print(leq_search(primes, 0, len(primes), 97))
    # exit()

    primes = prime_set()
    primes_set = set(primes)
    len_primes = len(primes)

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

    # output = 0
    likes = []
    for x in primes[1:]:
        if (x+1) // 2 in primes_set:
            likes.append(x)
    n_likes = len(likes)
    # print(likes)

    for i in range(Q):
        left_idx = geq_search(likes, 0, n_likes, l[i])
        right_idx = leq_search(likes, 0, n_likes, r[i])

        output = right_idx - left_idx + 1 if right_idx >= left_idx else 0
        print(output)

    # for i in range(Q):
    #     output = 0

    #     left, right = l[i], r[i]
    #     while True:
    #         if left in primes_set:
    #             break

    #         left += 2
    #     while True:
    #         if right in primes_set:
    #             break

    #         right -= 2

    #     left_idx = bin_search(primes, 0, len_primes, left)
    #     right_idx = bin_search(primes, 0, len_primes, right)

    #     for x in primes[left_idx:right_idx+1]:
    #         if (x + 1) // 2 in primes_set:
    #             output += 1

    #     print(output)
    # # return output


main()
# print(main())

Submission status: Accepted

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

max = 100001
prime = primes(max)
a = [0]*max
for i in range(max):
    if i % 2 == 0:
        continue
    if prime[i] and prime[(i+1)//2]:
        a[i] = 1

s = [0]*(max+1)
for i in range(max):
    s[i+1] = s[i] + a[i]

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

Submission status: Accepted

Solution code:
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

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


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


q = int(input())
for _ in range(q):
    L, R = map(int, input().split())
    ans = S[R]-S[L-1]
    print(ans)

Submission status: Accepted

Solution code:
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

primes = [p for p, tf in enumerate(is_prime) if tf]


A = [0]*(10**5+1)
for prime in primes:
    if is_prime[(prime+1)//2]:
        A[prime] = 1


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


q = int(input())
for _ in range(q):
    L, R = map(int, input().split())
    ans = S[R]-S[L-1]
    print(ans)

Submission status: Accepted

Solution code:
q = int(input())


def is_prime(x):
    if x == 1:
        return False
    d = 2
    while d**2 <= x:
        if x % d == 0:
            return False
        d += 1
    else:
        return True

primes = []
for x in range(2, 10**5+1):
    if is_prime(x):
        primes.append(x)
        
A = [0]*(10**5+1)
for prime in primes:
    if is_prime((prime+1)//2):
        A[prime] = 1


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


ans = []
for _ in range(q):
    L, R = map(int, input().split())
    cnt = S[R]-S[L-1]
    ans.append(cnt)

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