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

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

p = primes(max(r))
cnt = [0 for i in range(max(r)+1)]
for i in p:
    if (i + 1) // 2 in p:
        cnt[i]+=1

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

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

Submission status: Accepted

Solution code:
#nの素数判定
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 

q = int(input())
lr = []
minimum = float('inf')
maximum = 0
for _ in range(q):
    l, r = map(int, input().split())
    minimum = min(minimum, l)
    maximum = max(maximum, r)
    lr += [[l, r]]

prime = {i: 0 for i in range(1, maximum+1)}

for i in range(1, maximum+1):
    if is_prime(i) and is_prime((i+1)//2):
        prime[i] = 1

cum_prime = {i: 0 for i in range(1, maximum+1)}
cum_prime[minimum] = prime[minimum]
for i in range(1, maximum):
    cum_prime[i+1] = prime[i+1] + cum_prime[i]

cum_prime[0] = 0
for l, r in lr:
    print(cum_prime[r]-cum_prime[l-1])

Submission status: Accepted

Solution code:
import sys 

input = sys.stdin.readline
# sys.setrecursionlimit(25000)

q = int(input())
qry = [None] * q


mn = 10 ** 5
mx = 0
for i in range(q):
    qry[i] = list(map(int, input().split()))
    if qry[i][0] < mn:
        mn = qry[i][0]
    if qry[i][1] > mx:
        mx = qry[i][1]

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


cum = [0] * (mx + 1)
cum[0] = 0

for i in range(1, len(cum)):
    d = 0
    if i % 2 == 0:
        d = 0
    if is_prime(i) and is_prime((i + 1) // 2):
        d = 1
    cum[i] = cum[i - 1] + d

for i in range(q):
    print(cum[qry[i][1]] - cum[qry[i][0] - 1])

Submission status: Accepted

Solution code:
d = [0]
ans = 0

def prime(n):
    if n == 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        else:
            i += 1
    return True
    
for i in range(10 ** 5 // 2):
    if prime(2 * i + 1) and prime(i + 1):
        ans += 1
    d.append(ans)

Q = int(input())

for _ in range(Q):
    l, r = map(int, input().split())
    print(d[r // 2 + 1] - d[l // 2 + 1 - 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):
        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=primes(10**5)
accum=[0]*(10**5+1)
s=set(p)
for i in range(1,10**5+1):
  if i%2:
    if i in s and (i+1)//2 in s:
      accum[i]+=1
for i in range(10**5):
  accum[i+1]+=accum[i]
for _ in range(q):
  l,r=map(int,input().split())
  if l==1:
    print(accum[r])
  else:
    print(accum[r]-accum[l-1])

Submission status: Accepted

Solution code:
def erat(n):
    l = [0, 0] + [1 for _ in range(n - 1)]
    i = 2
    while (i < n + 1):
        if l[i] == 1:
            for j in range(i**2, n + 1, i):
                l[j] = 0
        i += 1

    return l


n_max = 10**5
is_prime = erat(n_max)
is_2017 = [0 for _ in range(n_max + 1)]
for i in range(2, n_max + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        is_2017[i] = 1

s = [0]
for i in range(1, n_max + 1):
    s.append(s[i - 1] + is_2017[i])

q = int(input())
for _ in range(q):
    li, ri = map(int, input().split())
    print(s[ri] - s[li - 1])

Submission status: Accepted

Solution code:
def get_prime_list(n):
    l = [0 for _ in range(n)]
    i = 1
    while (i < n):
        for j in range(2, int((i + 1)**0.5) + 1):
            if not (i + 1) % j:
                break
        else:
            l[i] = 1
        i += 1

    return l


n_max = 10**5
is_prime = get_prime_list(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1

s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])

q = int(input())
for _ in range(q):
    li, ri = map(int, input().split())
    print(s[ri] - s[li - 1])

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
queue = [list(map(int, input().split())) for _ in range(N)]


max_N = 100100
prime = np.ones(max_N, dtype=int)
a = np.zeros(max_N, dtype=int)
b = np.zeros(max_N+1, dtype=int)

prime[0], prime[1] = 0, 0
for i in range(2, max_N):
    if i == 0:
        continue
    for j in range(i*2, max_N, i):
        prime[j] = 0

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

for i in queue:
    print(b[i[1]+1]-b[i[0]])

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
queue = [list(map(int, input().split())) for _ in range(N)]


max_N = 100100
prime = list(np.ones(max_N, dtype=int))
a = list(np.zeros(max_N, dtype=int))
b = list(np.zeros(max_N+1, dtype=int))

prime[0], prime[1] = 0, 0
for i in range(2, max_N):
    if i == 0:
        continue
    for j in range(i*2, max_N, i):
        prime[j] = 0

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

for i in queue:
    print(b[i[1]+1]-b[i[0]])

Submission status: Accepted

Solution code:
Q = int(input())
N = int(10e5)

queries = []

def get_all_prime_numbers(N):
    values = list(range(1, N + 1))
    flags = [1] * N
    flags[0] = 0  # delete 1
    for i in range(N):
        if flags[i] == 0:
            continue

        prime = values[i]
        for mult in range(2, N // prime + 1):
            cand = mult * prime
            if flags[cand - 1] == 1:
                flags[cand - 1] = 0

    prime_numbers = []
    for i in range(N):
        if flags[i] == 1:
            prime_numbers.append(values[i])
    return prime_numbers

prime_numbers_list = set(get_all_prime_numbers(N))

accum_sum = [0]  # should contain accumulated sum for [], [1], [1, 3], [1, 3, 5], ...
for i in range(N // 2):
    num = 2 * i + 1
    if num in prime_numbers_list and (num + 1) // 2 in prime_numbers_list:
        accum_sum.append(accum_sum[-1] + 1)
    else:
        accum_sum.append(accum_sum[-1])

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

Submission status: Accepted

Solution code:
from collections import Counter
ma = 100000

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 is_prime[i] == False:
            continue
            
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
            
    return [i for i in range(n) if is_prime[i]]

q = int(input())
a = primes(100000)
b = []
for i in a:
    b.append(i*2 - 1)
    
aa = Counter(a)
bb = Counter(b)

rui = [0] * (ma+1)
for i in range(1,ma+1):
    if aa[i] == 1 and bb[i] == 1:
        rui[i] = rui[i-1] + 1
    else:
        rui[i] = rui[i-1]
        
for _ in range(q):
    l , r = map(int,input().split())
    print(rui[r] - rui[l-1])

Submission status: Accepted

Solution code:
def solve():
    n_max = 10 ** 5
    is_prime = sieve(n_max)
    is_like_2017 = [False] * (n_max+1)

    for i in range(n_max+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            is_like_2017[i] = True

    l = [0] * (n_max+1)
    r = [0] * (n_max+1)
    for i in range(1,n_max+1):
        if is_like_2017[i]:
            l[i] = l[i-1] + 1
        else:
            l[i] = l[i-1]

    for i in range(n_max-1,-1,-1):
        if is_like_2017[i]:
            r[i] = r[i+1] + 1
        else:
            r[i] = r[i+1]
    
    r.append(r[-1])

    Q = int(input())
    ans = []
    for i in range(Q):
        mn, mx = map(int,input().split())
        ans.append(l[-1] - l[mn-1] - r[mx+1])
    
    print(*ans, sep='\n')

# エラトステネスの篩
# n以下の素数を全列挙
# O(nloglogn)
def sieve(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False

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

    return is_prime

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
Q = int(input())
l = []
r = []
for i in range(Q) :
    p, q = map(int,input().split())
    l.append(p)
    r.append(q)

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    while True:
      if search_list[0]**2 > number:
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

primes = get_primenumber(10**5+1)
like2017 = [0 for _ in range(10**5+1)]

for p in primes :
    if (p+1)//2 in primes :
        like2017[p] = 1

like2017s = list(itertools.accumulate(like2017))

for i in range(Q) :
    print(like2017s[r[i]] - like2017s[l[i]-1])

Submission status: Accepted

Solution code:
MAX = 10**5 + 1
##下準備(素数判定)(https://python.ms/eratosthenes/#_1-%E7%B0%A1%E5%8D%98%E3%81%AA%E3%82%82%E3%81%AE)
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
a = primes(MAX)
prime = [0]*MAX
for i in range(1,MAX,2):
    if a[i] == 1 and a[int((i+1)/2)] == 1:
        prime[i] = 1
##下準備(累積和)
tmp = 0
csum = [0]*MAX
for i in range(MAX):
    if prime[i] == 1:
        tmp += 1
    csum[i] = tmp
csum.pop()

##入出力
Q = int(input())
lr = []
for i in range(Q):
    lr.append(list(map(int,input().split())))
for i in range(Q):
    print(csum[lr[i][1]]-csum[lr[i][0]-1])

Submission status: Accepted

Solution code:
Q = int(input())
R = 10**5 + 10

def getPrimes():
    isPrime = [True] * R
    ret = []
    for i in range(2, R):
        if not isPrime[i]:
            continue
        ret.append(i)
        for j in range(i, R, i):
            isPrime[j] = False
    return set(ret)

P = getPrimes()

def isOk(n):
    return n in P and (n + 1) // 2 in P

A = [0] * R
for i in range(R):
    if isOk(i):
        A[i] += 1

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

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

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

Submission status: Accepted

Solution code:
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=sorted(list(primes))
checker0=[0]*(n+1)
checker=[0]*(n+1)
for p in primes:
    checker0[p]=1
    if p%2==1 and checker0[(p+1)//2]==1:
        checker[p]=1

import numpy as np
cumcheck=np.cumsum(checker)
#print(cumcheck[0:100])
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(cumcheck[r]-cumcheck[l-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
p = [1]*100000
p[0] = 0
p[1] = 0
p[2] = 1
for i in range(3,100000):
    if i%2==0:
        p[i]=0
    if p[i]==1:
        j = i + i
        while j < 100000:
            p[j] = 0
            j += i
a = [0]*100000
for i in range(2,100000):
    if i % 2 ==0:
        continue
    if p[i] and p[(i+1)//2]:
        a[i] = 1
s = [0]*100001
for i in range(2,100000):
    s[i+1]=s[i]+a[i]
#print(s)
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:

is_prime = [True] * (10**5+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2,int(10**2.5)+1):
    if is_prime[i]:
        for j in range(i * 2, 10**5 + 1, i):
            is_prime[j] = False

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

for i in range(3,10**5+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        c+=1
    s[i]=c
for i in range(int(input())):
    l,r=map(int,input().split())
    print(s[r]-s[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = lambda: sys.stdin.readline().rstrip()


def eratosthenes(n):
    is_prime = [1] * (n + 1)

    is_prime[0] = 0
    is_prime[1] = 0

    ans = [0] * (n+1)

    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 = 10 ** 5


is_prime = eratosthenes(MAX)

a = [0] * (MAX+1)
for i in range(MAX+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1

s = list(accumulate(a))


Q = int(input())

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())
import math
import numpy as np
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 is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
for i in range(1,10**5,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

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

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = lambda: sys.stdin.readline().rstrip()

MAX = 10 ** 5

def eratosthenes(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        


Q = int(input())

is_prime = eratosthenes(MAX)

a = [0] * (MAX+1)
for i in range(MAX+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1
s = a
s = list(accumulate(s))

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

Submission status: Accepted

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

#import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
#from collections import deque, defaultdict, Counter
#from heapq import heappush, heappop
#from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
#from operator import itemgetter as ig

#sys.setrecursionlimit(10 ** 7)
#nf = 10 ** 20
#INF = float("INF")
#mod = 10 ** 9 + 7

'''
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]
# 深さ優先探索
def dfs(G, v):
    global time, first_order,seen,last_order
    time += 1
    first_order[v-1] = time   #　行きがけ

    seen[v-1] = True # v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)

    time += 1
    last_order[v - 1] = time  # 帰りがけ
'''

def main():

    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

    Q = int(input())
    task = []
    m = 10**20
    M = 0
    for i in range(Q):
        task.append(list(map(int, input().split())))
        m = min(task[i][0], m)
        M = max(task[i][1], M)

    A = [0]
    count = 0
    for i in range(m, M+1):
        if i % 2 != 0:
            if is_prime((i+1)/2) == True and is_prime(i) == True:
                count += 1
                A.append(count)
            else:
                A.append(count)
        else:
            A.append(count)


    for i in range(Q):
        ans = A[task[i][1]-m +1] -A[task[i][0]-m]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = 10**5+1
    p = 2
    f = [1]*(n+1)
    f[0] = 0
    f[1] = 0
    while p <= n:
        while p <= n and not f[p]:
            p += 1
        j = 2*p
        while j <= n:
            f[j] = 0
            j += p
        p += 1
    s = [1 if f[i] and f[(i+1)>>1] and i&1 else 0 for i in range(n+1)]
    for i in range(n):
        s[i+1] += s[i]
    q = I()
    for _ in range(q):
        l,r = LI()
        print(s[r]-s[l-1])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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


def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []

    for i in range(65):
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)
        for j in range(limit):
            if j >= len(A):
                break
            if A[j] % prime == 0:
                A.pop(j)
                continue

    for a in A:
        P.append(a)

    return P


def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    # 見つからなかったとき
    return None


MAX = 10 ** 5
prime_list = eratosthenes(MAX)
cumsum = [0] * ((MAX + 1) // 2)
cnt = 0

for i in range(1, MAX, 2):
    if binary_search(prime_list, i) and binary_search(prime_list, (i + 1) / 2):
        cnt += 1
    cumsum[(i - 1) // 2] = cnt

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    if l == 1:
        ans = cumsum[(r - 1) // 2]
    else:
        ans = cumsum[(r - 1) // 2] - cumsum[(l - 3) // 2]
    print(ans)

Submission status: Accepted

Solution code:
import random
def is_prime(q, k=5):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

q = int(input())
l, r = [0]*q, [0]*q
for i in range(q):
    il, ir = map(int, input().split())
    l[i], r[i] = il, ir

cnt = [0] * (10**5+1)
cnt[0], cnt[1], cnt[2] = 0, 0, 0
for i in range(3, 10**5+1):
    if i % 2 == 0:
        cnt[i] = cnt[i-1]
    else:
        if is_prime(i):
            if is_prime((i+1)//2):
                cnt[i] = cnt[i-1] + 1
            else:
                cnt[i] = cnt[i-1]
        else:
            cnt[i] = cnt[i-1]

for i in range(q):
    print(cnt[r[i]] - cnt[l[i]-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=[0]*100000
S=[0]*100001
for i in range(100000):
  if is_prime(i+1) and is_prime((i+2)/2):
    L[i]=1
L[1]=0    
for i in range(len(L)):
  S[i+1]=S[i]+L[i]
  
#print(L[:50],S[:50])
for i in range(Q):
  l,r=map(int, input().split())
  print(S[r]-S[l-1])

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    q = int(input())
    prime = [False] * 100001
    count = [0] * 100001
    prime[2] = True

    for i in range(3, 100001, 2):
        for j in range(3, int(i**0.5)+1, 2):
            if i % j == 0:
                break
        else:
            prime[i] = True

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#084_D
from bisect import bisect_left, bisect_right
prime = []
like_2017 = []

def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
            if (i+1)//2 in prime:
                like_2017.append(i)
                
sieve(100000)
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(bisect_right(like_2017, r)-bisect_left(like_2017, l))

Submission status: Accepted

Solution code:
from itertools import accumulate

def primes(n):
  prime = ([False]*2) + ([True]*(n-2))
  for i in range(2, n):
    if prime[i]:
      for j in range(i*2, n, i):
        prime[j] = False
  return prime

MAX = (10**5)+1
is_prime = primes(MAX)
q = int(input())
A = [1 if is_prime[i] and is_prime[(i + 1)//2] else 0 for i in range(MAX)]
S = [0] + list(accumulate(A))

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

for qi in Q:
    print(S[qi[1]+1]-S[qi[0]])

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

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

MAX = (10**5)+1
q = int(input())
A = [1 if is_prime(i)and is_prime((i + 1)//2) else 0 for i in range(MAX) ]
S = [0] + list(accumulate(A))

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

for qi in Q:  
    print(S[qi[1]+1]-S[qi[0]])

Submission status: Accepted

Solution code:
import sys

def PrimeNumber(max_number):
    # エラトステネスの篩
    is_prime = [True] * (max_number + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(max_number**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, max_number + 1, i):
            is_prime[j] = False

    return is_prime
#    return [i for i in range(max_number + 1) if is_prime[i]]

prime_checker = PrimeNumber(10**5)

# for i in range(11):
#     print(prime_checker[i])

like_2017 = [0] * (10**5+1)

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

# print("")
# for i in range(11):
#     print(like_2017[i])


sum_like_2017 = [0] * (10**5+1)

# 累積和
for i in range(10 ** 5):
    sum_like_2017[i+1] = sum_like_2017[i] + like_2017[i]

# print("")
# for i in range(11):
#     print(sum_like_2017[i])

Q = int(input())
for i in range(Q):
    start, end = map(int, input().split())
    print(sum_like_2017[end+1] - sum_like_2017[start])

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,n+1):
        if i*i>n:
            break
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    Q=int(readline())
    l=[0]*Q
    r=[0]*Q
    for i in range(Q):
        l[i],r[i]=map(int,readline().split())

    is_prime=primes(10**5)
    S=[0]*(10**5+1)
    for n in range(3,10**5+1):
        S[n]=S[n-1]
        if is_prime[n] and is_prime[(n+1)//2]:
            S[n]+=1

    for i in range(Q):
        print(S[r[i]]-S[l[i]-1])
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(1, 10**5, 2):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n = [0,0,1] + [1 for _ in range(10**5-2)]

def check_prime(x):
    for i in range(x*2,10**5+1,x):
        n[i] = 0

check_prime(2)
for i in range(3,int(math.sqrt(10**5))+1,2):
    check_prime(i)

c = [0 for _ in range(10**5+1)]
for i in range(1,10**5+1):
    c[i] = c[i-1] + (n[i] * n[(i+1)//2])

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

Submission status: Accepted

Solution code:
import math
import bisect
import heapq
from collections import deque

def prime_list(n):
    l = [True for _ in range(n+1)]
    l[0] = False
    l[1] = False
    for i in range(2,n+1):
        if l[i]:
            for j in range(2*i,n+1,i):
                l[j] = False

    return l

p = prime_list(10**5)

like = [0 for _ in range(10**5 + 1)]
for i in range(3,10**5+1,2):
    if p[i] and p[(i+1)//2]:
        like[i] = 1

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

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