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: Time Limit Exceeded

Solution code:
Q = int(input())
left = []
right = []
for a in range(Q):
    l,r = map(int,input().split())
    left.append(l)
    right.append(r)

import math

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


# 整数xが素数かどうかを判定する
def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True


if __name__ == '__main__':

    ls = [x for x in range(100000) if is_prime(x)]

for j in range(Q):
    width = right[j]-left[j]
    count = 0
    k = 0
    for k in range(width+1):
        if left[j]+k in ls and int((left[j]+k+1)/2) in ls:
            count+=1
        else:
            pass
    print(count)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input().strip())

def is_prime(tar):
    #mid = int(pow(tar,0.5))
    if tar < 2:
        return False
    for div in range(2,tar):
        if tar % div == 0:
            return False
    return True


count = 0

for i in range(0,Q):
    l,r = map(int,input().strip().split())
    for i in range(l, r + 1):
        if i % 2 == 0:
            continue
        if is_prime(i) and is_prime((i + 1) // 2):
            count += 1
    print(count)
    count = 0

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math

primes = [-1 for i in range(100000)]

def is_prime(x):
    global primes

    if primes[x] != -1:
        return primes[x] == 1

    if x < 2:
        primes[x] = 0
        return False
    if x == 2 or x == 3 or x == 5:
        primes[x] = 1
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        primes[x] = 0
        return False

    sx = math.sqrt(x)
    prime = 7
    step = 4
    while prime <= sx:
        if x % prime == 0:
            primes[x] = 0
            return False

        prime += step
        step = 6 - step

    primes[x] = 1
    return True

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

#    r_max = 100000
#    primes = [True for i in range(r_max)]
#    primes[0] = False
#    primes[1] = False
#    i = 2
#    max_i = int(math.sqrt(r_max))
#    while i <= max_i:
#        for j in range(i * i, r_max, i):
#            primes[j] = False
#        while i <= max_i:
#            i += 1
#            if primes[i]:
#                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if is_prime(j) and is_prime(int((j + 1) / 2)):
                c += 1
        print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math

primes = [-1 for i in range(100000)]

def is_prime(x):
    global primes

    if primes[x] != -1:
        return primes[x] == 1

    if x < 2:
        primes[x] = 0
        return False
    if x == 2 or x == 3 or x == 5:
        primes[x] = 1
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        primes[x] = 0
        return False

    sx = math.sqrt(x)
    prime = 7
    step = 4
    while prime <= sx:
        if x % prime == 0:
            primes[x] = 0
            return False

        prime += step
        step = 6 - step

    primes[x] = 1
    return True

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        sa = input().split(' ')
        l.append(int(sa[0]))
        r.append(int(sa[1]))

#    r_max = 100000
#    primes = [True for i in range(r_max)]
#    primes[0] = False
#    primes[1] = False
#    i = 2
#    max_i = int(math.sqrt(r_max))
#    while i <= max_i:
#        for j in range(i * i, r_max, i):
#            primes[j] = False
#        while i <= max_i:
#            i += 1
#            if primes[i]:
#                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if is_prime(j) and is_prime(int((j + 1) / 2)):
                c += 1
        print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


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


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if primes[i] * 2 - 1 in primes:
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0] - 1])

Submission status: Time Limit Exceeded

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


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


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if primes[i] * 2 - 1 in primes:
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0] - 1])