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:
Q = int(input())
queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r))

N = 10**5 + 1
is_prime = [True] * N
is_prime[0] = False
is_prime[1] = False
for i in range(4, N, 2):
    is_prime[i] = False
for i in range(3, N, 2):
    if i*i > N: break
    if is_prime[i]:
        for j in range(2*i, N, i):
            is_prime[j] = False

def is_ok(x):
    if (x % 2 == 0) or not is_prime[x]:
        return False
    return is_prime[(x + 1) // 2]

cum_ok = [None] * N
c = 0
for i in range(N):
    if is_ok(i):
        c += 1
    cum_ok[i] = c

for l, r in queries:
    print(cum_ok[r] - cum_ok[l-1])

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n): #nまでの素数列挙
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return is_prime 


def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

po = make_primes(10**5)

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

q = onem()

for i in range(1,10**5+1):
    dp[i] = dp[i-1]
    if i % 2 != 0:
        if po[i] and po[(i+1)//2]:
            dp[i] += 1


for i in range(q):
    x,y = m()
    print(dp[y]-dp[x-1])

Submission status: Accepted

Solution code:
import sys
Q = int(input())
input = sys.stdin.readline


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


M = [0] * (10**5+1)
for i in range(2, 10**5+1):
    M[i] = M[i-1]
    if len(prime_factorize(i)) == 1 and len(prime_factorize((i+1)//2)) == 1:
        M[i] += 1

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [0] * (n+1)
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[int((i+1)/2)]:
            solve[i] = 1
        
    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10 ** 5
is_prime = primes(L)
solve = like2017(is_prime,L)
# print(solve)
ans = list(accumulate(solve))
# print(ans)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False

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

Q = ii()
lr = li2(Q)

prime = sieve(10**5)
flag = [0]*(10**5+1)

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

flag = list(accumulate(flag))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

'''
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    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
    return is_prime
'''

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False

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


Q = ii()
lr = li2(Q)

prime = sieve(10**5)
flag = [0]*(10**5+1)

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

ans = list(accumulate(flag))

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

Submission status: Accepted

Solution code:



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

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

for n in range(2, 10**5+1):
    if not is_prime[n]:
        continue

    tmp = 2
    while n * tmp <= 10**5:
        is_prime[n * tmp] = False
        tmp += 1


cnt_accum_primes = [0] * (10**5 + 5)

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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

Q = ii()
lr = li2(Q)
from collections import deque
que = deque()

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 = [0]*(10**5+1)
flag = [0]*(10**5+1)
prime[2] = 1

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

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

ans = list(accumulate(flag))

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from itertools import accumulate
    from math import sqrt

    def Eratosthenes(x: int) -> set:
        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 main():
    import sys
    input = sys.stdin.buffer.readline
    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:
q = int(input())


from math import sqrt
M = 10**6
p = [1]*(M+1)
p[0] = p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0


ansl = []
ans = 0

for i in range(10**5+1):
    if i % 2 == 1:
        if p[i] == 1 and p[(i+1) // 2] == 1:
            ans += 1
    ansl.append(ans)

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

Submission status: Accepted

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

for i in range(1,10**5+1,2):
    if is_prime(i) and is_prime((i+1)/2):
        memo[i]=1
from itertools import accumulate
ac=list(accumulate(memo))

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

Submission status: Accepted

Solution code:
import math
import bisect
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())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [False] * (10 ** 5)


for i in range(1, 10 ** 5 + 1, 2):
    if not flags[i]:
        flag1 = is_prime(i)
        flag2 = is_prime((i + 1) // 2)
        if flag1 and flag2:
            flags[i] = True
True_idxs = []
for i in range(len(flags)):
    if flags[i]:
        True_idxs.append(i)

# print(True_idxs)

for l, r in lr_list:
    l_idx = bisect.bisect_left(True_idxs, l)
    r_idx = bisect.bisect_right(True_idxs, r)
    print(r_idx - l_idx)

Submission status: Accepted

Solution code:
lim = 10 ** 5
prime = [1] * (lim + 1) 
like = [0] * (lim + 1)
prime[0] = 0
prime[1] = 0

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

for i in range(3, lim + 1, 2):
    if prime[i] and prime[(i + 1) // 2]:
        like[i] = 1

for i in range(2, lim + 1):
    like[i] += like[i - 1]

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

Submission status: Accepted

Solution code:
import math, bisect
Q = int(input())
N = 10**5 + 1
P = set([2])
for k in range(3,N+1,2):
    f = 1
    for l in range(2,int(math.sqrt(k))+1):
        if k % l == 0:
            f = 0
            break
    if f==1:
        P.add(k)

R = []
for k in range(1,N,2):
    if k in P:
        if (k+1)//2 in P:
            R.append(k)

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

Submission status: Accepted

Solution code:
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # n以下の素数のリストprimes
    n = 10**5
    primes = set(range(2, n + 1))

    # 合成数 x は p<=x**0.5を満たす素因子 p をもつという性質を利用
    for i in range(2, int(n ** 0.5 + 1)):
        primes.difference_update(range(i * 2, n + 1, i))
    primes = list(primes)

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

    from itertools import accumulate


    B = [0] + L
    B = list(accumulate(B))  # 累積和を格納したリスト作成

    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り

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


resolve()

Submission status: Accepted

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

MAGIC_NUMBER = 100000
isprime = [True] * (MAGIC_NUMBER + 1)
for p in range(2, MAGIC_NUMBER + 1):
    if not isprime[p]: continue
    i_p = 2
    while p * i_p <= MAGIC_NUMBER:
        isprime[p * i_p] = False
        i_p += 1

primes = []
for p in range(2, MAGIC_NUMBER + 1):
    if isprime[p]: primes.append(p)

candidates = []
for p in primes:
    if p % 2 == 0: continue
    #
    if isprime[(p + 1) // 2]: candidates.append(p)


import bisect
    
for i, (li, ri) in enumerate(lr):
    i_l = bisect.bisect_left(candidates, li)
    i_r = bisect.bisect_left(candidates, ri)
    #
    if i_r < len(candidates) and candidates[i_r] == ri: i_r += 1
    print(i_r - i_l)

Submission status: Accepted

Solution code:
def prime(x):
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True
c = [0]*100002
for k in range(2,100001):
    if prime(k):
        c[k]=1


pri = [0]*100002
for i in range(2,100001):
    if c[i]==1 and c[(i+1)//2]==1:
        pri[i] = pri[i-1] +1 
    else:
        pri[i] = pri[i-1]

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

Submission status: Accepted

Solution code:
q= int(input())
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

X = []
for n in range(1, 10**5+1):
    if n%2 == 0:
        continue
    if is_prime(n) and is_prime((n+1)//2):
        X.append(n)

#print(X[0:15])
import bisect
for i in range(q):
    l, r = map(int, input().split())
    il = bisect.bisect_left(X, l)
    ir = bisect.bisect_right(X, r)
    print(ir-il)

Submission status: Accepted

Solution code:
def isPrime(n):
    """素数判定
    """
    if n < 2:
        return 0
    elif n == 2:
        return 1
    if n%2 == 0:
        return 0
    for i in range(3, int(n**0.5)+1, 2):
        if n%i == 0:
            return 0
    return 1


Q = int(input())
like2017 = [0]*(10**5+1)  # like2017[x]: 1以上x以下の2017に似た数の個数
res = 0

for i in range(1, 10**5):
    if i % 2 == 1:
        if isPrime(i) and isPrime((i+1)//2):
            res += 1
    like2017[i] = res

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    isPrime = [True] * (1 + 10**5)
    isPrime[0] = isPrime[1] = False
    Like = [0] * (1 + 10 ** 5)

    for i in range(2, 1 + 10 ** 5):
        if isPrime[i]:
            k = 2 * i
            while k <= 10 ** 5:
                isPrime[k] = False
                k += i
            if i % 2 == 1 and isPrime[(i + 1) // 2]: Like[i] = Like[i-1] + 1
            else: Like[i] = Like[i-1]
        else: Like[i] = Like[i-1]
                
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(Like[r] - Like[l-1])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np
from math import sqrt
def isPrime(n):
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
def main():
    q = int(input())
    Q = [list(map(int, input().split())) for _ in range(q)]
    a = np.array([1 if i%2 == 1 and isPrime(i) and isPrime((i+1)//2) else 0 for i in range(10**5+1)])
    np.cumsum(a, out=a)
    for l, r in Q:
        print(int(a[r] - a[l-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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


def main():
    import sys
    input = sys.stdin.buffer.readline
    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
    from itertools import accumulate
    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:
Q = int(input())
R = 10**5 + 100

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

isPrime = getPrimes()
A = [1 if i % 2 == 1 and isPrime[i] and isPrime[(i + 1) // 2] else 0 for i in range(R)]
accA = [0] * R
for i in range(1, R):
    accA[i] = accA[i - 1] + A[i - 1]
accA = accA[1:]

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

Submission status: Accepted

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

MAXN = 10**5+10
sieve = [0,0] + [1]*MAXN
p = 2
while p*p <= MAXN:
    if sieve[p]:
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

likes = [0] * MAXN
for i in range(3,MAXN,2):
    if sieve[i] and sieve[(i+1)//2]:
        likes[i] += 1
cl = [0]
for l in likes:
    cl.append(l + cl[-1])

ans = []
for l,r in LR:
    ans.append(cl[r+1] - cl[l])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from itertools import chain, accumulate


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


U = 10 ** 5 + 10
primes = prime_set(U)
memo = [0] * U
for i in range(1, U, 2):
    if i in primes and (i + 1) // 2 in primes:
        memo[i] = 1
memo = list(accumulate(memo))

Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(memo[r] - memo[l - 1])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e%p != 0]

_primes = eratosthenes(10**5+1)
primes = [False]*(10**5+1)
for p in _primes:
    primes[p] = True
    
like_2017 = [False] * (10**5+1)

for p in _primes:
    if primes[(p+1)//2]:
        like_2017[p] = True
    
c = 0
C = [0]
for i in range(1,10**5+1):
    if like_2017[i]:
        c += 1
    C.append(c)

q = int(input())
for i in range(q):
    left,right = map(int,input().split())
    print(C[right]-C[left-1])

Submission status: Accepted

Solution code:
lim = 10 ** 5
ans = [0] * (lim + 1)
like = [1] * (lim + 1)
like[0] = 0
like[1] = 0
for i in range(2, lim + 1):
    if like[i]:
        for j in range(i ** 2, lim + 1, i):
            like[j] = 0

for i in range(3, lim + 1, 2):
    if like[i] and like[(i + 1) // 2]:
        ans[i] = 1

for i in range(2, lim + 1):
    ans[i] += ans[i - 1]

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

Submission status: Accepted

Solution code:
from itertools import accumulate
def is_prime(n):
    is_prime = [True for i in range(n)]
    is_prime[0] = False
    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = i * 2
            while j <= n:
                is_prime[j - 1] = False
                j += i
    prime = [i for i in range(1, n + 1) if is_prime[i - 1]]
    return is_prime, prime
q = int(input())
l = [0]*q
r = [0]*q
for i in range(q):
    l[i], r[i] = list(map(int, input().split()))
is_prime, prime = is_prime(max(r))
like2017 = [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]):
            like2017[i] = 1
like2017 = [0] + like2017
like2017 = list(accumulate(like2017))
for i in range(q):
    print(like2017[r[i] + 1] - like2017[l[i]])

Submission status: Accepted

Solution code:
prime = [1 for i in range(int(1e5 + 10))]

def sieve(n):
    prime[0] = prime[1] = 0
    for i in range(2, n):
        for j in range(i + i, n, i):
            prime[j] = 0

q = int(input())
sieve(int(1e5))
cnt = []
for i in range(int(1e5)):
    if(i == 0):
        cnt.append(0)
    else:
        cnt.append(cnt[-1] + (prime[i] and prime[(i + 1) // 2]))
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[r] - cnt[l - 1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
U=10**5
is_prime=[True]*(U+1)
is_prime[0]=False
is_prime[1]=False
for p in range(2,U+1):
    if p*p>U:
        break
    if is_prime[p]:
        for j in range(p*p,U+1,p):
            is_prime[j]=False

is_2017like=[0]*(U+1)
for p in range(1,U+1):
    if (p+1)//2>U:
        break
    tmp=(is_prime[p] and is_prime[(p+1)//2])
    is_2017like[p]=is_2017like[p-1]+tmp
    
for i in range(int(input())):
    l,r=map(int,input().split())
    ans=is_2017like[r]-is_2017like[l-1]
    print(ans)

Submission status: Accepted

Solution code:
U=10**5
is_prime=[True]*(U+1)
is_prime[0]=False
is_prime[1]=False
for p in range(2,U+1):
    if p*p>U:
        break
    if is_prime[p]:
        for j in range(p*p,U+1,p):
            is_prime[j]=False

is_2017like=[0]*(U+1)
for p in range(1,U+1):
    if (p+1)//2>U:
        break
    tmp=(is_prime[p] and is_prime[(p+1)//2])
    is_2017like[p]=is_2017like[p-1]+tmp
    
for i in range(int(input())):
    l,r=map(int,input().split())
    ans=is_2017like[r]-is_2017like[l-1]
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
prime = [0]
for i in range(3, 100001, 2):
    count = 0
    count2 = 0
    for j in range(1, int(i ** 0.5) + 1):
        if i % j == 0:
            count += 1
    for j in range(1, int(((i+1)//2) ** 0.5) + 1):
        if ((i+1)//2) % j == 0:
            count2 += 1
    if count == count2 == 1:
        prime.append(1)
    else:
        prime.append(0)

def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums

prime = cum_sum(prime)
for i in range(n):
    l,r = map(int,input().split())
    print(prime[r//2+1]- prime[l//2])

Submission status: Accepted

Solution code:
import math
Q = int(input())
is_prime = [False] * (10**5+1)
is_prime[2] = True
is_like_2017 = [0] * (10**5+1)
for i in range(3, 10**5+1, 2):
    is_like_2017[i] = is_like_2017[i-2]
    for j in range(3, math.floor(math.sqrt(i))+1, 2):
        if i % j == 0:
            break
    else:
        is_prime[i] = True
        if is_prime[(i+1)//2]:
            is_like_2017[i] += 1
for _ in range(Q):
    l, r = map(int, input().split())
    if l-2 >= 0:
        print(is_like_2017[r] - is_like_2017[l-2])
    else:
        print(is_like_2017[r])

Submission status: Accepted

Solution code:
class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  # 素数を探す
            if f[i]: continue
            primes.append(i)
            f[i] = i  # 素数には自身を代入
            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む
                if not f[j]:
                    f[j] = i  # 最小の素因数を代入
        self.primes = primes
        self.f = f

    def is_prime(self, x) -> bool:  # 素数判定
        return self.f[x] == x

    def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]
        res = []
        while x != 1:
            res.append(self.f[x])
            x //= self.f[x]
        return res

    def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]
        fl = self.factor_list(x)
        if not fl: return []
        res = [[fl[0], 0]]
        for p in fl:
            if res[-1][0] == p:
                res[-1][1] += 1
            else:
                res.append([p, 1])
        return res


def main():
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

    MX = 10 ** 5

    s = Sieve(MX)

    like2017 = [0] * (MX + 1)
    for x in range(1, MX + 1, 2):
        if s.is_prime(x) and s.is_prime((x + 1) // 2):
            like2017[x] = 1

    *acc, = accumulate(like2017)

    Q = int(input())

    ans = []
    for _ in range(Q):
        left, right = map(int, input().split())
        res = acc[right] - acc[left - 1]
        ans.append(res)

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


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

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

c = [0]*(100000+1)
for i in range(2,100000+1):
    if pri[i]==1 and pri[(i+1)//2]==1:
        c[i] = c[i-1]+1
    else:
        c[i] = c[i-1]

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

Submission status: Accepted

Solution code:
import numpy as np
MAX_N=10**5
prime=np.full(MAX_N+1,True)
prime[:2]=False #0,1をFalseにしてる
for p in range(2,int(MAX_N**.5)+1):
  if prime[p]:
    prime[p*p::p]=False #p:素数の倍数をFalseに変える

like2017=np.zeros(MAX_N+1,dtype=np.int64)
for p in range(1,MAX_N+1):
  if 2*p>MAX_N:  #(p+1)//2をpとよみかえると、pと2*p-1になる
    break
  if prime[p] and prime[2*p-1]:
    like2017[2*p-1]=1

like2017_cumsum=like2017.cumsum()

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

Submission status: Accepted

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

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

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

for i in range(q):
    print(ruiseki[lr[i][1]] - ruiseki[lr[i][0] - 1])

Submission status: Accepted

Solution code:
import numpy as np
def isprime(x):
  if x<=1:return False
  if x==2:return True
  for i in range(2,int(x**0.5)+1):
    if x%i==0:return False
  return True

#リスト作成
prime=[isprime(i) for i in range(10**5+1)]

def like2017(x):
  return (prime[x] and prime[(x+1)//2])

a=[like2017(i) for i in range(10**5+1)]

ac=np.cumsum(a)

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

Submission status: Accepted

Solution code:
#import numpy as np
def isprime(x):
  if x<=1:return False
  if x==2:return True
  for i in range(2,int(x**0.5)+1):
    if x%i==0:return False
  return True

prime=[isprime(i) for i in range(10**5+1)]

def like2017(x):
  return (prime[x] and prime[(x+1)//2])

a=[like2017(i) for i in range(10**5+1)]

ac=[0]*(10**5+1)
for i in range(2,10**5+1):
  ac[i]=ac[i-1]+a[i]
#print(a[:10])
#print(ac[:10])
#a_cum=np.cumsum(a)

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

Submission status: Accepted

Solution code:
#import numpy as np
def isprime(x):
  if x<=1:return False
  if x==2:return True
  for i in range(2,int(x**0.5)+1):
    if x%i==0:return False
  return True

def like2017(x):
  return (isprime(x) and isprime((x+1)//2))

a=[like2017(i) for i in range(10**5+1)]

ac=[0]*(10**5+1)
for i in range(2,10**5+1):
  ac[i]=ac[i-1]+a[i]
#print(a[:10])
#print(ac[:10])
#a_cum=np.cumsum(a)

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