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:
import sys 
from itertools import accumulate
input=sys.stdin.readline
Q=int(input().rstrip())
S=[list(map(int,input().rstrip().split())) for _ in range(Q)]


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]]
    is_prime=[False]+is_prime
    return is_prime, table


def resolve():
    maxN=10**5+1
    booltable1,table1=sieve(maxN)
    booltable2,table2=sieve((maxN+1)//2)
    booltable=[0 for _ in range(maxN+1)]
    for i in range(1,maxN+1,2):
        booltable[i]=booltable1[i] and booltable2[(i+1)//2]
    # 累積和
    #booltable=[0]+booltable
    cumsum = list(accumulate(booltable))

    for i in range(Q):
        print(cumsum[S[i][1]]-cumsum[S[i][0]-1])
    
import sys
from io import StringIO
import unittest

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:
MAXN = 10**5 + 1

# c[i]: [0,i]での素数の個数
f = [False] * (MAXN)
for i in range(2,MAXN):
    if not f[i]:
        for j in range(i+i,MAXN,i):
            f[j] = True
c = [0] * (MAXN)
for i in range(3,MAXN):
    if not f[i] and not f[(i+1)//2]:
        c[i] += 1
    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:
Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

#エラトステネスの篩
p=[True]*(10**5+1)
p[0]=False
p[1]=False
for i in range(2,10**5+1):
    if p[i]:
        for j in range(2*i, 10**5+1, i):
            p[j]=False

#like2017[n]=n以下の「2017に似た数」の数
like2017=[0]*(10**5+1)
for i in range(1,10**5+1):
    like2017[i]=like2017[i-1]+(1 if i&1 and p[i] and p[(i+1)//2] else 0)

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

Submission status: Accepted

Solution code:
import sys
from math import floor, sqrt

def prime_nums(n):
    sieve = set(range(2, n + 1))
    non_prime = set(range(2 * 2, n + 1, 2))
    sieve -= non_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            non_prime = set(range(i * 2, n + 1, i))
            sieve -= non_prime
    return sieve

p = prime_nums(10**5)

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

q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2)

def main():
    for l, r in lr:
        yield cnt[r] - cnt[l-1]
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def eratosthenes_sieve(n):
    """ 素数列挙(エラトステネスの篩) """

    table = [0] * (n + 1)
    prime_list = []
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    return prime_list

MAX = 10 ** 5
# 素数列挙
primes = set(eratosthenes_sieve(MAX))
acc = [0] * (MAX+1)
for a in range(3, MAX+1, 2):
    # 条件を満たす数を確認
    if a in primes and (a + 1) // 2 in primes:
        acc[a] = 1
# 累積和
acc = list(accumulate(acc))

for i in range(INT()):
    l, r = MAP()
    # 各クエリO(1)で対応
    ans = acc[r] - acc[l-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect, bisect_left

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	primes = get_sieve_of_eratosthenes(10**5)

	prime_dict = dict(zip(primes, [1]*len(primes)))
	prime_2017 = []
	append = prime_2017.append
	for k in prime_dict.keys():
		if int((k+1)/2) in prime_dict:
			append(k)
	
	prime_2017.sort()
	# print(prime_2017)

	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(prime_2017, r)-bisect_left(prime_2017, l))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
q=int(input())

all=[]

#素数判定関数
def sosu(x):
  flag=True
  r=2
  while r*r<=x:
    if x%r==0:
      flag=False
      break
    r+=1
  return flag

for i in range(2,10**5+1):
  if i%2:
    if sosu(i)==True and (sosu((i+1)//2))==True:
      all.append(i)

import bisect

#print(all)

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

Submission status: Accepted

Solution code:

M=pow(10,5)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M)//i+1):
      prime_sieve[i*j]=1
#print(prime_sieve)
rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
       #print(i,sum)
  rangesum.append(sum)

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

Submission status: Accepted

Solution code:
primes = set(range(3, 10**5, 2))
primes.add(2)
cumsum = [0] * (10**5 + 2)

for i in range(3, 10**5):
    if i in primes:
        for not_prime in range(i+i, 10**5, i):
            primes.discard(not_prime)


count = 0
for num in range(1, 10**5, 2):
    if num in primes:
        if (num+1)//2 in primes:
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

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

Submission status: Accepted

Solution code:
def prime_table(n):
  list = [True for _ in range(n + 1)]
  list[0] = False
  list[1] = False
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1
  prime_cumsum = []
  amount = 0
  for i in range(len(list)):
    if(i == 0):
      prime_cumsum.append(0)
      continue
    if(list[i] == True and (i + 1) % 2 == 0 and list[(i+1)//2] ==True):
      amount +=1
    prime_cumsum.append(amount)
  return prime_cumsum

q = int(input())
question = [list(map(int, input().split())) for _ in range(q)]
prime = prime_table(10**5+1)
for l, r in question:
  print(prime[r] - prime[l-1])

Submission status: Accepted

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


cumsum = [0] * (10**5 + 2)

count = 0
for num in range(1, 10**5, 2):
    if is_prime(num):
        if is_prime((num+1)//2):
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

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

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input=sys.stdin.readline
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x+1)//2):
        return True
q=int(input())
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=map(int,input().split())
    print(acl[r]-acl[l-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x+1)//2):
        return True
q=int(input())
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=map(int,input().split())
    print(acl[r]-acl[l-1])

Submission status: Accepted

Solution code:
Q = int(input())

sl = 10**5 + 1

s = [i % 2 for i in range(sl)]
s[0] = s[1] = 0
s[2] = 1

for i in range(2, sl):
  if s[i] == 0: continue
  for j in range(2 * i, sl, i):
    s[j] = 0

dp = [0] * sl
for i in range(3, sl):
  dp[i] = dp[i-1] + (s[i] and s[(i+1)//2])

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

Submission status: Accepted

Solution code:

MAX = 10**5+1

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

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

likes = [0] * (MAX+1)
for i in range(0, MAX+1):
    if i % 2 == 0: continue
    if is_prime[i] and is_prime[(i+1)//2]:
        likes[i] = 1
    
c = [0] * (MAX+1)
for i in range(MAX):
    c[i+1] = c[i] + likes[i]

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

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

Submission status: Accepted

Solution code:
def d_2017_like_number():
    Q = int(input())
    I = [[int(i) for i in input().split()] for j in range(Q)]

    def prime_table(n):
        """n 以下の整数がそれぞれ素数かどうかのリスト (エラトステネスの篩)"""
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  # 0と1は素数でない
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  # jの倍数は素数でない
        return is_prime

    def calc_like2017(m, p):
        # i 番目の要素が、1 以上 i 以下の "2017に似た数" の個数となるリストを返す
        # m 以下の素数のリスト p を予め作っておく必要がある
        c = [0] * (m + 1)  # 0番目は0と定義する
        for i in range(3, m + 1, 2):  # 0, 1, 2 は定義上2017に似た数にならない
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, m + 1):
            c[i] += c[i - 1]
        return c

    like2017 = calc_like2017(10**5, prime_table(10**5))
    ans = [like2017[r] - like2017[l - 1] for l, r in I]
    return '\n'.join(map(str, ans))

print(d_2017_like_number())

Submission status: Accepted

Solution code:
import bisect,sys
from itertools import accumulate
input = sys.stdin.readline
def prime(n):
  prime_table = [2]
  for i in range(3,n+1):
    f = 1
    for j in prime_table[:bisect.bisect_right(prime_table,int(i**0.5))]:
      if i % j == 0:
        f = 0
        break
    if f:
      prime_table.append(i)
  return prime_table

q = int(input())
prime_table = prime(10**5)
like_2017 = [0]*(10**5+1)
for i in range(1,10**5+1,2):
  if i in prime_table and (i+1) //2 in prime_table:
    like_2017[i] = 1
like_2017 = list(accumulate(like_2017))
for i in range(q):
  l,r = map(int,input().split())
  print(like_2017[r] - like_2017[l-1])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
p = [2]
res = [0] * (pow(10, 5) + 1)
for i in range(3, pow(10, 5), 2):
  f = 0
  for x in p:
    if i % x == 0:
      f = 1
      break
  if f == 0: p.append(i)
ps = set(p)
for i in range(3, len(res) - 1):
  if i % 2 == 0: res[i] = res[i - 1]
  x = (i in ps) and (((i + 1) // 2) in ps)
  res[i] = res[i - 1] + x
#print(res[: 100])
for _ in range(N):
  a, b = map(int, input().split())
  print(res[b] - res[a - 1])

Submission status: Accepted

Solution code:
import math
q = int(input())
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_flag = [True] * (10 ** 5 + 1)
prime_flag[0] = False
prime_flag[1] = False
prime_cnt = [0] * (10 ** 5 + 1)

for i in range(2, math.ceil(math.sqrt(10 ** 5))):
    for j in range(i + i, 10 ** 5 + 1, i):
        prime_flag[j] = False


for i in range(2, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    num = (i + 1) / 2
    if num % 1 == 0 and prime_flag[i] and prime_flag[int(num)]:
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print(prime_cnt[right] - prime_cnt[left - 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())
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_cnt = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print(prime_cnt[right] - prime_cnt[left - 1])

Submission status: Accepted

Solution code:
def main():
    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())
    scope = [tuple(map(int, input().split())) for _ in range(q)]
    prime_cnt = [0] * (10 ** 5 + 1)
    for i in range(1, 10 ** 5 + 1):
        prime_cnt[i] = prime_cnt[i - 1]
        if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
            prime_cnt[i] += 1

    for i in range(q):
        left = scope[i][0]
        right = scope[i][1]
        print(prime_cnt[right] - prime_cnt[left - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
Q = int(input())
P = 10 ** 5
c1 = [i % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c1[2] = True
c2[3] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = i*2-1
        if ind < P:
            c2[ind] = True
        ind = i * 2
        while ind < P:
            c1[ind] = False
            ind += i
    if c1[i] and c2[i]:
        L.append(i)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_right(L, r) -  bisect_left(L, l))

Submission status: Accepted

Solution code:
C=[0]*(10**5+2)
C[0]=1
C[1]=1
s=[0]*(10**5+2)
S=[0]*(10**5+2)
t=1
while(t<=(10**5)):
    t+=1
    if(C[t]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k]=1

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

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

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

Submission status: Accepted

Solution code:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
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
n=10**5+2
a=sieve(n)
ans=[0]*(n//2)
for i in range(0,n,2):
    if a[i] and a[i//2]:
        ans[i//2]=1
#print(ans[:20])
for i in range(1,n//2):
    ans[i]+=ans[i-1]
#print(ans[:20])
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    if l==1:
        l=2
    if r==1:
        r=2
    print(ans[r//2]-ans[l//2 -1])

Submission status: Accepted

Solution code:
import math
import bisect
def seachPrimeNum(N):
    max = int(math.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

L=seachPrimeNum(10**5)
L=[i for i in L if (i+1)//2 in L]
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(bisect.bisect_right(L,r) - bisect.bisect_left(L,l))

Submission status: Accepted

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


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

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


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

Submission status: Accepted

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

max_val = max([lr[1] for lr in lr_list])

# エラトステネスの篩
num_list = list(range(max_val + 1))
for num in num_list[2:max_val // 2 + 1]:
    if num > 0:
        for i in range(num*2, max_val+1, num):
            num_list[i] = -1

prime_num_set = set([num for num in num_list if num>0][1:])

# 累積和
sum_list = [0, 0, 0]
for i in range(3, max_val+1):
    if i in prime_num_set and (i+1)//2 in prime_num_set:
        sum_list.append(sum_list[-1]+1)
    else:
        sum_list.append(sum_list[-1])

for l, r in lr_list:
    print(sum_list[r] - sum_list[l-1])

Submission status: Accepted

Solution code:
q = int(input())
F = [1]*(10**5)
for i in range(2,5*10**4):##2は素数
    F[i*2]=0

F[1]=0
for i in range(3,350,2):
    for n in range(3,10**5,2):
        if n>i and n%i==0:
            F[n]=0
#print(F[:10])
acc = 0
L =[0]
for i in range(1,10**5):
    if F[i] and F[(i+1)//2]:
        acc+=1
    L.append(acc)
L.append(0)
#print(L[:11])
for i in range(q):
    li,ri = map(int, input().split( ))
    print(L[ri]-L[li-1])

Submission status: Accepted

Solution code:
q=int(input())
max=100001
is_prime =[1]*max
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,max):
    if not is_prime[i]:
        continue
    for j in range(i*2,max,i):
        is_prime[j] = 0

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

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

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

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = True
show_flg = False


# エラトステネスのふるい 素数の列挙
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


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    prime_list = primes(10**5+1)
    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(prime_list[i] and prime_list[(i+1)//2]))
        else:
            arr.append(0)
    ARR = list(accumulate([0] + arr))

    for i in range(Q):
        # print(r[i]+1, l[i], ARR[r[i]+1], ARR[l[i]])
        # print(ARR[:r[i]+1])
        print(ARR[r[i]+1] - ARR[l[i]])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = True
show_flg = False


def is_prime(n):
    """
    nの素数判定
    :param int n:
    :rtype: Bool
    """
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(is_prime(i) and is_prime((i+1)//2)))
        else:
            arr.append(0)

    ARR = list(accumulate([0] + arr))
    # print(arr[:100])
    # print(ARR[:100])

    for i in range(Q):
        # print(r[i]+1, l[i], ARR[r[i]+1], ARR[l[i]])
        # print(ARR[:r[i]+1])
        print(ARR[r[i]+1] - ARR[l[i]])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def init_prime(n_max :int):
    """ https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
    # returns prime list [2..n_max]
    """
    if n_max <= 1: return []
    if n_max == 2: return [2,]
    prime = [2,]
    _app_p = prime.append
    limit = int(n_max**0.5)
    data = [i for i in range(3, n_max+1, 2)]
    while data:
        p = data[0]
        if p > limit:
            return prime + data
        _app_p(p)
        data = [e for e in data if e%p]

def main():
    N = 10**5
    vP = init_prime(N)
    sP = set(vP)

    vA = [0,]
    appA = vA.append
    cnt = 0
    for i in range(1, N+1):
        if i in sP and (i+1)//2 in sP:
            cnt += 1
        appA(cnt)

    #print(vA[:2018])###

    Q = int(input())
    vRes = []
    appRes = vRes.append
    for _ in range(Q):
        L, R = map(int, input().split())
        appRes(vA[R] - vA[L-1])
    print(*vRes, sep="\n")

if __name__ == "__main__":
    main()

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
S=[]
for i in range(1,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    S+=[i]
Count=[0]
count=0
for i in range(1,10**5):
  if i in S:
    count+=1
  Count +=[count]

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
q = int(input())
ls = []

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

pr = primes(10 ** 5)
pr = [j and pr[i*2-1] for i, j in enumerate(pr[:5*10**4+1])]
new_pr = [i for i in accumulate(pr)]

for i in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    print(new_pr[(r+1)//2] - new_pr[(l-1)//2])

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def main():
    N = [0] * (10 ** 5 + 1)
    for i in range(3, 10 ** 5 + 1, 2):
        if is_prime(i) and is_prime((i + 1) // 2):
            N[i] += 1

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




if __name__ == "__main__":
    main()