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: Wrong Answer

Solution code:

import math


def query(ql, qr, buckets, is_prime):
    ans = 0
    lb, rb = -1, -1
    for st, ed, count in buckets:
        # 左にはみ出している
        if st < ql <= ed and ed <= qr:
            for x in range(ql, ed + 1):
                ans += x % 2 and is_prime[x] and is_prime[(x + 1) // 2]

        # 完全に含まれていればそのままカウント
        if ql < st and ed < qr:
            ans += count

        # 右にはみ出している
        if ql < st and st <= qr < ed:
            for x in range(st, qr + 1):
                ans += x % 2 and is_prime[x] and is_prime[(x + 1) // 2]
        # 収まっている
        if st <= ql and qr <= ed:
            for x in range(ql, qr + 1):
                ans += x % 2 and is_prime[x] and is_prime[(x + 1) // 2]
            break
    return ans
        

def submit():
    n_max = 10**5

    # n_maxまでの素数を数える
    is_prime = {x: True for x in range(1, n_max + 1)}
    is_prime[1] = False
    for x in range(2, math.ceil(math.sqrt(n_max)) + 1):
        if is_prime[x]:
            y = 2 * x
            while y <= n_max:
                is_prime[y] = False
                y += x
    
    # バケット法で数えておく
    bucket_size = math.floor(math.sqrt(n_max))
    buckets = []
    for st in range(1, n_max + 1, bucket_size):
        ed = st + bucket_size - 1
        like2017s = [is_prime[x] and is_prime[(x + 1) // 2] for x in range(st, ed + 1) if x % 2 and x <= n_max]
        bucket_count = sum(like2017s)
        buckets.append([st, ed, bucket_count])
    
    # クエリを処理する
    q = int(input())
    queries = []
    for _ in range(q):
        queries.append(list(map(int, input().split())))
        
    for q in queries:
        res = query(q[0], q[1], buckets, is_prime)
        print(res)


submit()

Submission status: Wrong Answer

Solution code:
import math

def sieve(n):
    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 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

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

primes = sieve(10000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

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

Submission status: Wrong Answer

Solution code:
import math

def sieve(n):
    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 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

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

primes = sieve(10000 + 1)
c = [0] * (100000 + 2)

for i in range(3, len(primes)):
    is_prime = primes[i]
    if is_prime and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

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

Submission status: Wrong Answer

Solution code:
import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime

def sieve(n):
    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 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

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

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
minimum = 0
primes = sieve(maximum + 1)
print(primes)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
def primes_set(n):
    #
    prime_list = []
    non_prime_list = []
    k_list = []
    number_dict = {
        i: None for i in reversed(range(n + 1))}
    #
    del number_dict[0]
    del number_dict[1]
    while True:
        # get prime
        prime, _ = number_dict.popitem()
        prime_list.append(prime)
        if prime * prime > n:
            break

        # get non primes
        non_prime_list.append(prime * prime)
        while True:
            k, _ = number_dict.popitem()
            k_list.append(k)
            if prime * k > n:
                break
            non_prime_list.append(prime * k)

        while k_list:
            number_dict[k_list.pop()] = None

        # delete non prime
        while non_prime_list:
            del number_dict[non_prime_list.pop()]

    while number_dict:
        prime, _ = number_dict.popitem()
        prime_list.append(prime)

    return set(prime_list)


p_set = primes_set(10 ** 5)
sum_list = [0] * ((10 ** 5) + 1)

for i in range(len(sum_list) - 1):
    if (i+1) in p_set and ((i+2) // 2) in p_set:
        ret = 1
    else:
        ret = 0
    sum_list[i+1] = sum_list[i] + ret

q = int(input())

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

Submission status: Wrong Answer

Solution code:
def primes_set(n):
    #
    prime_list = []
    non_prime_list = []
    k_list = []
    number_dict = {
        i: None for i in reversed(range(n + 1))}
    #
    del number_dict[0]
    del number_dict[1]
    while True:
        # get prime
        prime, _ = number_dict.popitem()
        prime_list.append(prime)
        if prime * prime > n:
            break

        # get non primes
        non_prime_list.append(prime * prime)
        while True:
            k, _ = number_dict.popitem()
            k_list.append(k)
            if prime * k > n:
                break
            non_prime_list.append(prime * k)

        while k_list:
            number_dict[k_list.pop()] = None

        # delete non prime
        while non_prime_list:
            del number_dict[non_prime_list.pop()]

    while number_dict:
        prime, _ = number_dict.popitem()
        prime_list.append(prime)

    return set(prime_list)


p_set = primes_set(10 ** 5)
sum_list = [0] * ((10 ** 5) + 1)

for i in range(len(sum_list) - 1):
    if (i+1) in p_set and ((i+2) // 2) in p_set:
        ret = 1
    else:
        ret = 0
    sum_list[i+1] = sum_list[i] + ret

q = int(input())

ret = []

for i in range(q):
    l, r = map(int, input().split())
    ret.append(str(sum_list[r] - sum_list[l-1]))

print('\n'.join(ret))

Submission status: Wrong Answer

Solution code:
Q = int(input())
judge_arr = []
data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		if (i+1)/2 in prime_arr:
			prime_arr.append(i)
			#judge_arr.append(1)
		else:
			prime_arr.append(i)
			#judge_arr.append(0)

Submission status: Wrong Answer

Solution code:
Q = int(input())
judge_arr = []
data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		#if (i+1)/2 in prime_arr:
		prime_arr.append(i)

Submission status: Wrong Answer

Solution code:
Q = int(input())
judge_arr = []
data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		#if (i+1)/2 in prime_arr:
		prime_arr.append(i)
			#judge_arr.append(1)
		#else:
			#prime_arr.append(i)
			#judge_arr.append(0)

#for n in range(len(prime_arr)):
	#if (prime_arr[n]+1)/2 in prime_arr:
		#judge_arr[n] = 1

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

for x in range(Q):
	num = 0
	print(sumz(data[x][0],data[x][1]+1))

Submission status: Wrong Answer

Solution code:
Q = int(input())
judge_arr = []
data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		if (i+1)/2 in prime_arr:
			prime_arr.append(i)
			#judge_arr.append(1)
		else:
			prime_arr.append(i)
			#judge_arr.append(0)

#for n in range(len(prime_arr)):
	#if (prime_arr[n]+1)/2 in prime_arr:
		#judge_arr[n] = 1

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

for x in range(Q):
	num = 0
	print(sumz(data[x][0],data[x][1]+1))

Submission status: Wrong Answer

Solution code:
Q = int(input())
judge_arr = []
data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		if (i+1)/2 in prime_arr:
			prime_arr.append(i)
			judge_arr.append(1)
		else:
			prime_arr.append(i)
			judge_arr.append(0)

#for n in range(len(prime_arr)):
	#if (prime_arr[n]+1)/2 in prime_arr:
		#judge_arr[n] = 1

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)


def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

judge_arr = [0]*len(prime_arr)
for n in range(len(prime_arr)):
	if (prime_arr[n]+1)/2 in prime_arr:
		judge_arr[n] = 1

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return  (((a+1)/2 in prime_arr))

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

judge_arr = [0]*len(prime_arr)
for n in range(len(prime_arr)):
	if judge(prime_arr[n]):
		judge_arr[n] = 1

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return  (((a+1)/2 in prime_arr))

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	return sum(judge_arr[x+1:y])

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number+100,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return ((a in prime_arr)) and (((a+1)/2 in prime_arr))

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	#print(x+1,y-1)
	#print(prime_arr[x+1],prime_arr[y-1])
	return sum(judge_arr[x+1:y])

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number+100,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return ((a in prime_arr)) and (((a+1)/2 in prime_arr))

def sumz(a,b):
	x = 0
	y = 0
	for n in range(len(prime_arr)):
		if prime_arr[n]<a:
			x = n
		if prime_arr[n]>b:
			y = n
			break
	#print(x+1,y-1)
	#print(prime_arr[x+1],prime_arr[y-1])
	return sum(judge_arr[x+1:y])

judge_arr = [0]*len(prime_arr)
for n in range(len(prime_arr)):
	if prime_arr[n] in prime_arr and (prime_arr[n]+1)/2 in prime_arr:
		judge_arr[n] = 1


for x in range(Q):
	print(sumz(data[x][0],data[x][1]+1))

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number+100,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5 or i%j!=0:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number+100,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

Submission status: Wrong Answer

Solution code:
Q = int(input())

data = []
max_number = 0
for i in range(Q):
	x = input().split()
	data.append([int(x[0]),int(x[1])])
	if max_number<data[i][1]:
		max_number = data[i][1]


prime_arr = [2]

for i in range(3,max_number,2):
	c = 0
	for j in prime_arr:
		if j>i**0.5:
			break
		elif i%j==0:
			c = 1
	if c==0:
		prime_arr.append(i)

def judge(a):
	return (a in prime_arr) and ((a+1)/2 in prime_arr)

for x in range(Q):
	num = 0
	for y in range(data[x][0],data[x][1]+1,2):
		#print(y)
		if judge(y):
			num+=1
	print(num)

Submission status: Wrong Answer

Solution code:
CACHE = {}
def is_prime(n):
    if CACHE.get(n):
        return CACHE[n]
    i = 2
    while i * i <= n:
        if n % i == 0:
            CACHE[n] = False
            return False
        i += 1
    CACHE[n] = True
    return True

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

for l, r in LR:
    count = 0
    for i in range(l, r+1):
        if i % 2 == 1 and is_prime(i) and is_prime((i + 1) / 2):
            count+=1        
    print(count)

Submission status: Wrong Answer

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

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

for l, r in LR:
    count = 0
    for i in range(l, r+1):
        if i % 2 == 1 and is_prime(i) and is_prime((i + 1) / 2):
            count+=1        
    print(count)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False

# √size まで
for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(input())

for _ in range(Q):
  l, r = map(int, input().split())
  if l == r:
    print(1 if l in like_numbers else 0)
  else:
  	print(bisect_left(like_numbers, r) - bisect_left(like_numbers, l))

Submission status: Wrong Answer

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

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        num=int(i**0.5)
        like_num=(i+1)//2
        if like_num==1 or like_num%2==0:continue
        num2=int(like_num**0.5)
        for j in range(3,num+1,2):
            if i%j==0:break
        else:
            for j in range(2,num2+1):
                if like_num%j==0:break
            else:
                cnt+=1
                #print(i,cnt)
    print(cnt)

Submission status: Wrong Answer

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

for l,r in lr:
    cnt=0
    for i in range(l,r+1,2):
        num=int(i**0.5)
        like_num=(i+1)//2
        num2=int(like_num**0.5)
        for j in range(3,num+1,2):
            if i%j==0:break
        else:
            for j in range(2,num2+1):
                if like_num==2 or like_num%j==0:break
            else:
                cnt+=1
                #print(i,cnt)
    print(cnt)

Submission status: Wrong Answer

Solution code:
import math

q=int(input())
N=[0]*(10**5+1)
N[3]=1
N[2]=1
S=[]

for i in range(5,10**5+1,2):
    flag=True
    for j in range(3,int(math.sqrt(i))+1,2):
        if i%j==0:
            flag=False
            break
    if flag:
        N[i]=1

X=[0]*(10**5+1)
X[2]=1
cnt=0
for i in range(3,10**5+1,2):
    if N[i]==1 and N[(i+1)//2]==1:
        cnt+=1
    X[i]=cnt
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    print(X[l]-X[r-2])

Submission status: Wrong Answer

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())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(1, rmax+1):
    if is_prime(i) and (i+1) % 2 == 0 and is_prime((i+1)//2):
        csum.append(csum[i-1]+1)
    else:
        csum.append(csum[i-1])

print(csum)
for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]-1], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])

Submission status: Wrong Answer

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())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(1, rmax+1):
    if is_prime(i) and is_prime((i+1)/2):
        csum.append(csum[i-1]+1)
    else:
        csum.append(csum[i-1])

#print(csum)
for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]-1], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])

Submission status: Wrong Answer

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())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(1, rmax+1):
    if is_prime(i) and is_prime((i+1)/2):
        csum.append(csum[i-1]+1)
    else:
        csum.append(csum[i-1])

print(csum)
for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        #print(csum[lr[i][1]]-csum[lr[i][0]-1], lr[i][0],lr[i][1], csum[lr[i][0]], csum[lr[i][1]])

Submission status: Wrong Answer

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())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0,0]
for i in range(1,rmax+1):
    if is_prime(i) and is_prime((i+1)//2):
        csum.append(csum[i]+1)
    else:
        csum.append(csum[i])

#print(csum)
for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]+1]-csum[lr[i][1]])
        #print(csum[lr[i][1]+1]-csum[lr[i][1]], lr[i][1], csum[lr[i][1]-1],csum[lr[i][1]], csum[lr[i][1]+1])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]])

Submission status: Wrong Answer

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())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(rmax+1):
    if is_prime(i) and is_prime((i+1)//2):
        csum.append(csum[i]+1)
    else:
        csum.append(csum[i])

for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]+1]-csum[lr[i][1]])
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]])

Submission status: Wrong Answer

Solution code:
import math
def sosu(x):
  for i in range(2,math.ceil(x**(1/2)) + 1):
    if x % i == 0:
      return False
  return True

N = pow(10, 5)
lis = [0] * N
lis[1] = 1
for i in range(3,N+1):
  if i % 2 == 0:
    continue
  elif sosu(i) and sosu((i+1)//2):
    lis[i-1] = 1
ruiseki = [0]
total = 0
for i in range(N):
  total += lis[i]
  ruiseki.append(total)

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

Submission status: Wrong Answer

Solution code:
import math
def sosu(x):
  for i in range(2,math.ceil(x**(1/2)) + 1):
    if x % i == 0:
      return False
  return True

N = pow(10, 5)
lis = [0] * N
lis[1] = 1
for i in range(3,N+1):
  if i % 2 == 0:
    continue
  elif sosu(i) and lis[(i+1)//2-1] == 1:
    lis[i-1] = 1
ruiseki = [0]
total = 0
for i in range(N):
  total += lis[i]
  ruiseki.append(total)

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

Submission status: Wrong Answer

Solution code:
import math
def sosu(x):
  for i in range(2,math.ceil(x**(1/2)) + 1):
    if x % i == 0:
      return False
  return True

N = pow(10, 5)
lis = [0] * N
lis[1] = 1
for i in range(3,N+1):
  if i % 2 == 0:
    continue
  elif sosu(i) and lis[(N+1)//2-1] == 1:
    lis[i-1] = 1
ruiseki = [0]
total = 0
for i in range(N):
  total += lis[i]
  ruiseki.append(total)

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

Submission status: Wrong Answer

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):
    if lr[i][1] != lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]]+prime[lr[i][1]]+prime[lr[i][0]])
    else:
        print(prime[lr[i][0]])

Submission status: Wrong Answer

Solution code:
a=[]
for i in range(1,9999,2):
	if i<100:
		for j in range(2,i):
			if i%j==0:
				break
			if j==i-1:
				a.append(i)
	if i>100:
		for j in range(2,101):
			if i%j==0:
				break
			if j==100:
				a.append(i)

x=int(input())
ans=0
for k in range(x):
	ans=0
	y,z=list(map(int, input().split()))

	for m in range(y,z+1,2):
		if (m in a)==True and ((m+1)//2 in a)==True:
			ans=ans+1
	print(ans)

Submission status: Wrong Answer

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):
        if task[i][0] == task[i][1]:
            ans = A[task[i][1]-m] - A[task[i][0]-m]+1
        else:
            ans = A[task[i][1]-m] - A[task[i][0]-m]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from itertools import accumulate

def primes(n):
  
  prime = ([False]*2) + ([True]*(n-2))
  for i in range(2, int(math.sqrt(n))+1):
    if prime[i]:
      for j in range(i*2, int(math.sqrt(n))+1, 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)]
A[0] = 1
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: Wrong Answer

Solution code:
import math
from itertools import accumulate

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

MAX = (10**5)+1
is_prime = primes(MAX)
q = int(input())
A = [1 if is_prime[i] is True and is_prime[(i + 1)//2] is True 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: Wrong Answer

Solution code:
import math
from itertools import accumulate

def primes(n):
  prime = ([False]*2) + ([True]*(n-2))
  for i in range(2, int(math.sqrt(n))+1):
    if prime[i]:
      for j in range(i*2, int(math.sqrt(n))+1, 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: Wrong Answer

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

q = int(input())


def is_prime(n):
    prime = True

    for i in range(2, int(math.sqrt(n)) + 1):

        if n % i == 0:
            prime = False

    return prime


for i in range(q):
    count = 0
    l, r = map(int, input().split())

    for j in range(l, r + 1, 2):
        if is_prime(j) and is_prime(j * (j - 1) / 2):
            count += 1

    print(count)