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:
import sys
input = sys.stdin.readline

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a = primes(100000)
resemble = []
for i in a:
    if i == 2 or (i+1)//2 not in a:
        pass
    else:
        resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

Submission status: Time Limit Exceeded

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a = primes(100000)
resemble = []
for i in a:
    if i == 2 or (i+1)//2 not in a:
        pass
    else:
        resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

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:
#!/usr/bin/env python3
import math

def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

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

        prime += step
        step = 6 - step

    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:
#!/usr/bin/env python3
import math

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 primes[j] and primes[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

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 * 2, 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 primes[j] and primes[int((j + 1) / 2)]:
                c += 1
        print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def abc084_d():
    import numpy as np

    def prime_list(limit):
        if limit == 1:
            return []

        prime_nums = [2]
        for _i in range(3, limit + 1, 2):
            factor = False
            for divisor in range(3, int(_i ** 0.5) + 1, 2):
                if _i % divisor == 0:
                    factor = True

            if not factor:
                prime_nums.append(_i)

        return prime_nums

    q = int(input())
    l, r = [[None] * q for _ in range(2)]
    for i in range(q):
        l[i], r[i] = map(int, input().split())

    primes = np.array(prime_list(max(r)))
    for i in range(q):
        ans = 0
        candidates = primes[(l[i] <= primes) & (primes <= r[i])]
        for val in candidates:
            if (val + 1) // 2 in primes:
                ans += 1
        print(ans)


abc084_d()

Submission status: Time Limit Exceeded

Solution code:
def abc084_d():
    def prime_list(limit):
        if limit == 1:
            return []

        prime_nums = [2]
        for _i in range(3, limit + 1, 2):
            factor = False
            for divisor in range(3, int(_i ** 0.5) + 1, 2):
                if _i % divisor == 0:
                    factor =True

            if not factor:
                prime_nums.append(_i)

        return prime_nums

    q = int(input())
    l, r = [[None] * q for _ in range(2)]
    for i in range(q):
        l[i], r[i] = map(int, input().split())

    primes = prime_list(max(r))
    for i in range(q):
        ans = 0
        for j in range(l[i], r[i]+1):
            if j in primes and (j+1)//2 in primes:
                ans += 1
        print(ans)


abc084_d()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
q = int(input())
ql = []
R = 0
for _ in range(q):
    l,r = map(int, input().split())
    ql.append((l,r))
    R = max(R,r)
R += 1

is_prime = [True]*(R+1)
is_prime[0] = False
is_prime[1] = False
for n in range(2,R+1):
    if is_prime[n]:
        x = 2
        while n*x<R+1:
            is_prime[n*x] = False
            x += 1
primes = []
for i in range(len(is_prime)):
    if is_prime[i]:
        primes.append(i)

like2017 = [0]*(R+1)
for i in range(R):
    if i%2==1 and (i in primes) and ((i+1)//2 in primes):
        like2017[i+1] = like2017[i] + 1
    else:
        like2017[i+1] = like2017[i]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
q = int(input())
ql = []
R = 0
for _ in range(q):
    l,r = map(int, input().split())
    ql.append((l,r))
    R = max(R,r)
R += 1

primes = [2]
for n in range(3,R+1,2):
    flag = True

    for p in primes:
        if n%p==0:
            flag = False
            break
        if n<p*p:
            break

    if flag:
        primes.append(n)

like2017 = [0]*(R+1)
for i in range(R):
    if i%2==1 and (i in primes) and ((i+1)//2 in primes):
        like2017[i+1] = like2017[i] + 1
    else:
        like2017[i+1] = like2017[i]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
q = int(input())
ql = []
R = 0
for _ in range(q):
    l,r = map(int, input().split())
    ql.append((l,r))
    R = max(R,r)
R += 1

primes = []
for n in range(2,R+1):
    flag = True

    for p in primes:
        if n%p==0:
            flag = False
            break
        if n<p*p:
            break

    if flag:
        primes.append(n)

like2017 = [0]*(R+1)
for i in range(R):
    if i%2==1 and (i in primes) and ((i+1)//2 in primes):
        like2017[i+1] = like2017[i] + 1
    else:
        like2017[i+1] = like2017[i]

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