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 math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

def primes(n):
    isp = [True for _ in range(n+1)]
    isp[0] = False
    isp[1] = False
    l = ceil(sqrt(n))
    n += 1
    for i in range(2, l):
        if not isp[i]: continue
        for j in range(i*2, n, i): isp[j] = False
    return isp

q = int(input())
maxv = 10**5
isp = primes(maxv)
cnt = [0 for _ in range(maxv + 1)]

for i in range(3, maxv+1):
    if i%2 and isp[i] and isp[(i+1)//2]:
        cnt[i] = 1
#print(cnt[:10])
acc = list(accumulate(cnt))
for _ in range(q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])

Submission status: Accepted

Solution code:
def era(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = num**0.5

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

Q=int(input())
l=[]
r=[]
for _ in range(Q):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)
N=max(r)
input_list=era(N+1)
Prime=set([i for i, b in enumerate(input_list) if b == True])
cnt=[0,0,0]
for i in range(3,N+1):
    cnt.append(cnt[-1])
    if i%2==1 and i in Prime and (i+1)//2 in Prime:
        cnt[i]+=1
#print(Prime)
#print(cnt)
for j in range(Q):
    print(cnt[r[j]]-cnt[l[j]-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
q = int(input())
lr = []
for _ in range(q):
    l, r = map(int, input().split())
    lr.append((l, r))
primes = set(range(3, 10**5, 2))
primes.add(2)
for i in range(3, 10**5, 2):
    if i not in primes:
        continue
    for j in range(i*2, 10**5, i):
        primes.discard(j)
nums = []
for i in primes:
    if (i+1)//2 in primes:
        nums.append(i)
nums.sort()
for l, r in lr:
    print(bisect_right(nums, r)-bisect_left(nums, l))

Submission status: Accepted

Solution code:
def main():
    q = int(input())
    # 1~10**5 Eratosthenes
    ma = 10**5+1
    prime = [1]*ma # 1:prime 0:not prime
    prime[0],prime[1] = 0,0
    for i in range(2,ma):
        if prime[i] == 0:
            continue
        for j in range(i*2,ma,i):
            prime[j] = 0

    # like 2017
    like = [0]*ma # 1:like 0:not like
    for i in range(ma):
        if i%2 == 0: #odd only 
            continue
        if prime[i] == 1 and prime[(i+1)//2] == 1:
            like[i] = 1

    # ruiseki
    rui = [0]*(ma+1)
    for i in range(ma):
        rui[i+1] = rui[i]+like[i]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q = int(input())
maxn = 10**5
is_prime = [True if i%2 == 1 else False for i in range(0, maxn+1) ]
is_prime[0] = False
is_prime[1] = False
is_prime[2] = True
for i in range(3, int(maxn**0.5) + 1, 2):
    if not is_prime[i]:
        continue
    for j in range(i*2, maxn+1, i):
        is_prime[j] = False

ps = [i for i in range(maxn+1) if is_prime[i]]
ps = set(ps)

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

from itertools import accumulate
cs = list(accumulate(c))

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

Submission status: Accepted

Solution code:
import math
Q = int(input())

ps = []
maxfac = math.sqrt(10**5)
nums = [i+1 for i in range(1, 10**5)]
while True:
    p = nums[0]
    if maxfac <= p:
        break
    ps.append(p) 
    nums = [num for num in nums if num % p != 0]

ps = set(ps + nums)

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

from itertools import accumulate
cs = list(accumulate(c))

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

Submission status: Accepted

Solution code:
M = 10**6
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 4*10**4):
    if p[i]:
        for j in range(i*i, M, i):
            p[j] = 0
C = [0]*M
for i in range(2, M):
    if p[i] and p[(i+1)//2]:
        C[i] = C[i-1] + 1
    else:
        C[i] = C[i-1]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(C[r] - C[l-1])

Submission status: Accepted

Solution code:

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

N = int(1e+5)
max_num = int(N**0.5)
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2,max_num+1):
    if not is_prime[i]:
        continue
    for j in range(i*2,N+1,i):
        is_prime[j] = False

ans = [False] * (N+1)
for i in range(3,N+1,2):
    b = (i+1)//2
    if is_prime[i] and is_prime[b]:
        ans[i] = True

comurative_ans = [0] * (N+1)
sum_true = 0
for i in range(N+1):
    if ans[i] :
        sum_true += 1
    comurative_ans[i] = sum_true
for l,r in query:
    print(comurative_ans[r+1]-comurative_ans[l-1])