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 math
q=int(input())
lr=[list(map(int, input().split())) for i in range(q)]

l,r=[],[]
for a in lr:
    l.append(a[0])
    r.append(a[1])

ss = [i for i in range(1,max(r)+1)]
for i in range(2,int(math.sqrt(max(r)))+1):
    for j in range(2*i,max(r)+1,i):
        ss[j-1]=0
for j in range(q):
    ans=0
    for i in range(l[j],r[j]+1,2):
        if i in ss and (i+1)//2 in ss:
            ans+=1
    if l[j]==1:
        ans-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def primeJudge(p):  # 素数判定 素数なら True, 素数でないなら False
    p = abs(p)
    if p == 2:
        return True
    if p < 2 or p & 1 == 0:
        return False
    return pow(2, p-1, p) == 1


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = map(int, input().split())

for i in range(Q):
    tmp = 0
    for i in range(L[i], R[i] + 1):
        if primeJudge(int(i)) == True and primeJudge(int((i + 1) / 2)) == True:
            tmp += 1
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
P = [0] * 100001
Q = [0] * 100002
P[0] = 1
P[1] = 1

for i in range(2, 100000):
    if P[i] == 0:
        for j in range(i*2, 100000, i):
            P[j] += 1

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

for k in range(3, 100000, 2):
    if P[k] == 0 and P[(k + 1) // 2] == 0:
        Q[k] = 1

for l in range(n):
    print(sum(Q[:num[l][1]+1]) - sum(Q[:num[l][0]]))

Submission status: Time Limit Exceeded

Solution code:
P = [0] * 100001
Q = [0] * 100002
P[0] = 1
P[1] = 1

for i in range(2, 100000):
    if P[i] == 0:
        for j in range(i*2, 100000, i):
            P[j] += 1

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

for k in range(3, 100000, 2):
    if P[k] == 0 and P[(k + 1) // 2] == 0:
        Q[k] += 1

for l in range(n):
    print(Q[:num[l][1]+1].count(1) - Q[:num[l][0]].count(1))

Submission status: Time Limit Exceeded

Solution code:
n=10**5;p=[0,0]+[1]*n
for i in range(2,-~int(n**.5)):
    if p[i]:
        for j in range(i**2,-~n,i):p[j]=0
for _ in[0]*int(input()):
    l,r=map(int,input().split());c=0
    for x in range(l,-~r,2):
        if p[x] and p[-~x//2]:c+=1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

def primes(n):
    p = [2]
    for i in range(3, n, 2):
        is_prime = True

        for p_ in p:
            if p_**2 > i:
                break
            if i%p_ == 0:
                is_prime = False
                break
        if is_prime:
            p.append(i)
    return p

primes = primes(10**5)

count_list = []
count = 0
for i in range(10**5//2):
    if 2*i+1 in primes:
        if (i+1) in primes:
            count += 1
    count_list.append(count)

def solve():
    l, r = list(map(int, input().split()))
    if l == 1:
        print(count_list[r//2])
    else:
        print(count_list[r//2] - count_list[l//2-1])

for q in range(Q):
    solve()

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

def primes(n):
    p = [2]
    for i in range(3, n, 2):
        is_prime = True

        for p_ in p:
            if p_**2 > i:
                break
            if i%p_ == 0:
                is_prime = False
                break
        if is_prime:
            p.append(i)
    return p

primes = primes(10**5)

def solve():
    l, r = list(map(int, input().split()))

    count = 0
    for x in range(l, r+1, 2):
        if x in primes:
            if (x+1)/2 in primes:
                count += 1
    print(count)

for q in range(Q):
    solve()

Submission status: Time Limit Exceeded

Solution code:
primes = {2}
for i in range(1, 50000):
    i = 2 * i + 1
    for j in primes:
        if i % j == 0:
            break
    else:
        primes.add(i)

ret = set()
for i in primes:
    if (i + 1) // 2 in primes:
        ret.add(i)
ret = sorted(ret)


def binary(i):
    low = 0
    high = len(ret) - 1
    mid = 0
    while high - low > 1:
        mid = (high + low) // 2
        if ret[mid] < i:
            low = mid
        else:
            high = mid
    return low if ret[low] < i else -1


q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    low = binary(l)
    high = binary(r)
    high += 1 if ret[high+1] == r else 0
    print(high-low)

Submission status: Time Limit Exceeded

Solution code:
A = [2]
B = []
C = []

for x in range(3, 100000, 2):
    a = False
    for y in A:
        if y * y > x:
            a = True
            break
        if x % y == 0: break
    if a:
        A.append(x)

for i in range(len(A)):
    if (A[i]+1)/2 in A:
        B.append(A[i])

Q = int(input())

for i in range(Q):
    l,r = map(int, input().split())
    C.append(len([1 for j in B if (j>=l and j<=r)]))

for t in C:
    print(t)

Submission status: Time Limit Exceeded

Solution code:
import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
R=[S[:i+1].count(True) for i in range(M+1)]
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])

Submission status: Time Limit Exceeded

Solution code:
import math
def isprime(n):
    if n==1 or n==0:
        return False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0 and n!=i:
            return False
    return True


Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
for i in range(Q):
    l[i], r[i] = map(int, input().split())
X=max(r)
P=[0 for i in range(X+1)]
for i in range(X+1):
    if isprime(i) and i%2==1:
        if isprime((i+1)//2):
            P[i]+=1
S=[sum(P[:i+1]) for i in range(X+1)]
for i in range(Q):
    print(S[r[i]]-S[l[i]-1])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
prime = [2]
NUM2017 = []
def setPrime(TOP):
    for x in range(3,TOP+1):
        for y in range(len(prime)):
            if x%prime[y] == 0:
                break
            if y == len(prime)-1:
                prime.append(x)
                if int((x+1)/2) in prime:
                    NUM2017.append(x)
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = list(map(int,input().split()))

setPrime(max(r))

for n in range(Q):
    left = 0
    right = 0
    for m in range(len(NUM2017)):
        if NUM2017[m] < l[n]:
            left +=  1
            right += 1
        elif l[n] <= NUM2017[m] and NUM2017[m] <= r[n]:
            right += 1
        else:
            break
    print(right-left)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
prime = [2]
def setPrime(TOP):
    for x in range(3,TOP+1):
        for y in range(len(prime)):
            if x%prime[y] == 0:
                break
            if y == len(prime)-1:
                prime.append(x)
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = list(map(int,input().split()))

setPrime(max(r))

result = [0]*max(r)
for x in range(len(prime)):
    if int((prime[x]+1)/2) in prime:
        for y in range(prime[x]-1,max(r)):
            result[y] += 1

for n in range(Q):
    if l[n] > 1:
        print(result[r[n]-1]-result[l[n]-2])
    else:
        print(result[r[n]-1])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
prime = [2]

def setPrime(TOP):
    for x in range(3,TOP+1):
        for y in range(len(prime)):
            if x%prime[y] == 0:
                break
            if y == len(prime)-1:
                prime.append(x)
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = list(map(int,input().split()))

setPrime(max(r))

for n in range(Q):
    result = 0
    for m in range(l[n],r[n]+1):
        if m in prime and int((m+1)/2) in prime:
            result += 1
    print(result)

Submission status: Time Limit Exceeded

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

max_l = max(lr, key=lambda x:x[1])[1]

a = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%a[m-1] != 0,a[m:])
    a = a[:m]
    a.extend(b)
    m += 1
    if m > len(a):
        break

like2017 = [3]
for i in range(5,max_l+1,4):
    for j in a:
        if not ((i % j != 0 or i in a) and ((i+1)/2 % j != 0 or (i+1)/2 in a)):
            break
        if j == a[-1]:
            like2017.append(i)

for i in range(Q):
    print(len(list(filter(lambda x: lr[i][0] <= x <= lr[i][1],like2017))))

Submission status: Time Limit Exceeded

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

max_l = max(lr, key=lambda x:x[1])[1]

a = list(range(2,int(math.ceil(max_l**0.5)+1)))
prime = list(range(2,max_l+1))
i = 1
while True:
    b = filter(lambda x: x%a[i-1] != 0,a[i:])
    a = a[:i]
    a.extend(b)
    i += 1
    if i > len(a):
        break

for i in range(len(a)):
    prime = list(filter(lambda x: x%a[i] != 0 or x == a[i],prime))

like2017 = []
for i in prime:
    if (i+1)/2 in prime:
        like2017.append(i)

for i in range(Q):
    print(len(list(filter(lambda x: lr[i][0] <= x <= lr[i][1],like2017))))

Submission status: Time Limit Exceeded

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

max_l = max(lr, key=lambda x:x[1])[1]

a = list(range(2,int(math.ceil(max_l**0.5)+1)))
prime = list(range(2,max_l+1))
i = 1
while True:
    b = filter(lambda x: x%a[i-1] != 0,a[i:])
    a = a[:i]
    a.extend(b)
    i += 1
    if i > len(a):
        break

for i in range(len(a)):
    prime = list(filter(lambda x: x%a[i] != 0 or x == a[i],prime))

p = 0
count = {}
for i in range(1,max_l+2,2):
    if (i in prime) and ((i+1)/2 in prime):
        p += 1
    count[i] = p
count[-1] = 0
for i in range(Q):
    print(count[lr[i][1]]-count[lr[i][0]-2])

Submission status: Time Limit Exceeded

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

max_l = max(lr, key=lambda x:x[1])[1]

prime =[2]
for i in range(2,max_l+1):
    for j in prime:
        if i % j == 0:
            break
        else:
            if j == prime[-1]:
                prime.append(i)

p = 0
count = {}
for i in range(1,max_l+2,2):
    if (i in prime) and ((i+1)/2 in prime):
        p += 1
    count[i] = p
count[-1] = 0
for i in range(Q):
    print(count[lr[i][1]]-count[lr[i][0]-2])

Submission status: Time Limit Exceeded

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

max_l = max(lr, key=lambda x:x[1])[1]

prime =[2]
for i in range(2,max_l+1):
    for j in prime:
        if i % j == 0:
            break
        else:
            if j == prime[-1]:
                prime.append(i)

for i in range(Q):
    count = 0
    for j in range(lr[i][0],lr[i][1]+2,2):
        if (j in prime) and ((j+1)/2 in prime):
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

Q = int(input())

for i in range(Q):
    a, b = map(int,input().split())
    ans = 0
    while a <= b:
        if is_prime(a):
            if is_prime((a + 1) // 2):
                ans += 1
        a += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX=100001
array=[True for i in range(MAX)]
array[1]=False

for i in range(2, MAX):
	if array[i]:
		for j in range(2, int(MAX/i)+1):
			if(j*i < MAX):
				array[i*j]=False
Q=int(input())
for i in range(Q):
	l,r=map(int, input().split())
	count=0
	for j in range(l, r+1):
		if array[j] and array[int((j+1)/2)]:
			count+=1
	print(count)

Submission status: Time Limit Exceeded

Solution code:
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def decide_sosu(max_num):
	sosus_nokori = range(2, max_num + 1)
	sosus = []
	while len(sosus_nokori) > 0:
		min_i = min(sosus_nokori)
		sosus.append(min_i)
		sosus_nokori.remove(min_i)
		for num in range(min_i*min_i, max_num+1, min_i):
			if num in sosus_nokori:
				sosus_nokori.remove(num)
	return sosus

sosus = decide_sosu(max_num+1)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (i in sosus) & (((i+1) % 2)==0) & ((i+1)/2 in sosus): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]

Submission status: Time Limit Exceeded

Solution code:
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def decide_sosu(max_num):
	sosus_nokori = range(2, max_num + 1)
	sosus = []
	while len(sosus_nokori) > 0:
		min_i = min(sosus_nokori)
		sosus.append(min_i)
		for num in range(min_i, max_num+1, min_i):
			if num in sosus_nokori:
				sosus_nokori.remove(num)
	return sosus

sosus = decide_sosu(max_num+1)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (i in sosus) & (((i+1) % 2)==0) & ((i+1)/2 in sosus): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]

Submission status: Time Limit Exceeded

Solution code:
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def decide_sosu(max_num):
	sosus = []
	for i in range(2, max_num + 1):
		flag = 0
		for num in sosus:
			if i % num == 0:
				flag = 1
				break
		if flag == 0:
			sosus.append(i)
	return sosus

sosus = decide_sosu(max_num+1)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (i in sosus) & (((i+1) % 2)==0) & ((i+1)/2 in sosus): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
li = []
M = 0
for index in range(Q):
	l, r = map(int, input().split())
	li.append((l, r))
	M = max([M, l, r])

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
cut_root = math.sqrt(M+1)
for prime in primes:
	if prime > cut_root:
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0
similar_2017 = [0 for _ in range(M+1)]
similar_2017[3] = 1
for i in range(5, M+1, 4):
	if primes[i] != 0:
		if primes[(i+1)//2] != 0:
			similar_2017[i] = 1

for l, r in li:
	print(sum(similar_2017[l:r+1]))

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())
li = []
M = 0
for index in range(Q):
	l, r = map(int, input().split())
	li.append((l, r))
	M = max([M, l, r])

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
for prime in primes:
	if prime > math.sqrt(M):
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0

for l, r in li:
	count = 0
	for i in range(l,r+1,2):
		if primes[i] != 0 and primes[(i+1)//2] != 0:
			count += 1
	print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

isprime = None

def sieve(n):
    global isprime

    if n < 2:
        isprime = [False] * (n + 1)
        return

    isprime = [True if i % 2 != 0 else False for i in range(n + 1)]
    isprime[0] = isprime[1] = False
    isprime[2] = True

    from math import sqrt, ceil

    for i in range(3, int(sqrt(n)) + 1):
        if isprime[i] == True:
            for j in range(2, ceil(n / i)):
                isprime[i * j] = False

def main():
    global isprime

    sieve(100000)

    _ = sys.stdin.readline()

    accsums = [0] * 100001
    k = 2
    for l, r in (map(int, line.split()) for line in sys.stdin.readlines()):
        if r > k:
            for i in range(k, r + 1):
                accsums[i] = accsums[i - 1]
                if isprime[i] == isprime[(i + 1) // 2] == True:
                     accsums[i] += 1
        print(accsums[r] - accsums[l - 1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

isprime = None

def sieve(n):
    global isprime

    if n < 2:
        isprime = [False] * (n + 1)
        return

    isprime = [True if i % 2 != 0 else False for i in range(n + 1)]
    isprime[0] = isprime[1] = False
    isprime[2] = True

    from math import sqrt, ceil

    for i in range(3, int(sqrt(n)) + 1):
        if isprime[i] == True:
            for j in range(2, ceil(n / i)):
                isprime[i * j] = False

def main():
    global isprime

    sieve(100000)

    _ = sys.stdin.readline()

    for l, r in (map(int, line.split()) for line in sys.stdin.readlines()):
        cnt = 0
        for i in range(l, r + 1):
            if isprime[i] == isprime[(i + 1) // 2] == True:
                cnt += 1
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

def make_prime_list(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

def main():
    Q = int(input())

    is_prime = defaultdict(lambda: False)
    primes = make_prime_list(100000)
    for prime in primes:
        is_prime[prime] = True

    query_list = []
    for i in range(Q):
        query_list.append([int(_) for _ in input().split()])

    for query in query_list:
        begin = query[0]
        end   = query[1] + 1

        n_like_2017 = 0
        for target in range(begin, end, 2):
            if (is_prime[target]) and (is_prime[(target + 1) // 2]):
                n_like_2017 += 1

        print(n_like_2017)

main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

def make_prime_list(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

def main():
    Q = int(input())

    like_2017_list = []

    is_prime = defaultdict(lambda: False)
    primes = make_prime_list(100000)
    for prime in primes:
        is_prime[prime] = True

    query_list = []
    for i in range(Q):
        query_list.append([int(_) for _ in input().split()])

    for query in query_list:
        begin = query[0]
        end   = query[1] + 1

        n_like_2017 = 0
        for target in range(begin, end, 2):
            if target in like_2017_list:
                n_like_2017 += 1
                continue

            if (is_prime[target]) and (is_prime[(target + 1) // 2]):
                like_2017_list.append(target)
                n_like_2017 += 1

        print(n_like_2017)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

is_prime_list = {
    1: False
}

def is_prime(x):
    global is_prime_list

    if x in is_prime_list:
        return is_prime_list[x]

    for divisor in range(2, math.floor(math.sqrt(x))+1):
        if x % divisor == 0:
            is_prime_list[x] = False
            return is_prime_list[x]

    is_prime_list[x] = True
    return is_prime_list[x]

def main():
    Q = int(input())

    like_2017_list = []

    query_list = []
    for i in range(Q):
        query_list.append([int(_) for _ in input().split()])

    for query in query_list:
        begin = query[0]
        end   = query[1] + 1

        like_2017 = 0
        for target in range(begin, end, 2):
            if target in like_2017_list:
                like_2017 += 1
                continue

            if is_prime(target) and is_prime((target + 1) // 2):
                like_2017_list.append(target)
                like_2017 += 1

        print(like_2017)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

is_prime_list = {
    1: False
}

def is_prime(x):
    global primes

    if x in is_prime_list:
        return is_prime_list[x]

    for divisor in range(2, math.floor(math.sqrt(x))+1):
        if x % divisor == 0:
            is_prime_list[x] = False
            return is_prime_list[x]

    is_prime_list[x] = True
    return is_prime_list[x]

def main():
    global primes

    Q = int(input())

    query_list = []
    for i in range(Q):
        query_list.append([int(_) for _ in input().split()])

    for query in query_list:
        begin = query[0]
        end   = query[1] + 1

        like_2017 = 0
        for target in range(begin, end, 2):
            if is_prime(target) and is_prime((target + 1) // 2):
                like_2017 += 1

        print(like_2017)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


primes = eratosthenes(10 ** 5+1)
like2017 = list(filter(lambda x: (x+1)/2 in primes, primes))
num_like2017 = len(like2017)

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    left = bisect.bisect_left(like2017, l)
    right = num_like2017 - bisect.bisect_right(like2017, r)

    print(num_like2017 - left - right)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
TLE
"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5))

    # 10000ごとのブロックに分けて答えを計算しておく
    p_numbers = []
    block_size = 10000
    for i in range(0, 10**5, block_size):
        ans = 0
        for j in range(i, i + block_size):
            if j in primes and ((j+1)//2) in primes:
                ans += 1
        p_numbers.append(ans)


    for l, r in queries:
        t1 = ceil(l / block_size) * block_size
        t2 = floor(r / block_size) * block_size

        if t1 >= t2:
            ans = 0
            for i in range(l, r+1, 2):
                if i in primes and ((i+1)//2) in primes:
                    ans += 1
            print(ans)
        else:
            ans = 0
            for i in range(l, t1, 2):
                if i in primes and ((i+1)//2) in primes:
                    ans += 1
            for i in range(t2+1, r, 2):
                if i in primes and ((i+1)//2) in primes:
                    ans += 1
            for i in range(t1//block_size, t2//block_size):
                ans += p_numbers[i]
            print(ans)


def main(args):
    queries = []
    Q = int(input())
    # Q = 0
    # queries.append((12351, 89999))
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
TLE
"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5))

    # 1000ごとのブロックに分けて答えを計算しておく
    p_numbers = []
    block_size = 1000
    for i in range(0, 10**5, block_size):
        ans = 0
        for j in range(i, i + block_size):
            if j in primes and ((j+1)//2) in primes:
                ans += 1
        p_numbers.append(ans)


    for l, r in queries:
        t1 = ceil(l / block_size) * block_size
        t2 = floor(r / block_size) * block_size
        if t1 >= t2:
            ans = 0
            for i in range(l, r+1, 2):
                if i in primes and ((i+1)//2) in primes:
                    ans += 1
            print(ans)
        else:
            ans = 0
            for i in range(l, t1, 2):
                if i in primes and ((i+1)//2) in primes:
                    ans += 1
            for i in range(t2+1, r, 2):
                if i in primes and ((i+1)//2) in primes:
                    ans += 1
            for i in range(t1//block_size, t2//block_size):
                ans += p_numbers[i]
            print(ans)


def main(args):
    queries = []
    Q = int(input())
    # Q = 0
    # queries.append((53241, 99999))
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d

"""
import sys
from sys import stdin
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5))
    for l, r in queries:
        ans = 0
        for i in range(l, r+1, 2):
            if i in primes and ((i+1)//2) in primes:
                ans += 1
        print(ans)


def main(args):
    queries = []
    Q = int(input())
    # Q = 0
    # queries.append((1, 99999))
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
#   for j in range(3, int(i**0.5)+1, 2):
   for j in prime_number:
      if j > int(i**0.5)+1:
         break
      elif i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in like_number:
      if lr[i][1] >= j:
         if lr[i][0] <= j:
            count = count + 1
      else:
         break
   print(count)

Submission status: Time Limit Exceeded

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

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
   for j in range(3, int(i**0.5)+1, 2):
      if i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in like_number:
      if lr[i][1] >= j:
         if lr[i][0] <= j:
            count = count + 1
      else:
         break
   print(count)

Submission status: Time Limit Exceeded

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

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
   for j in range(3, int(i**0.5)+1, 2):
      if i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in range(lr[i][0], lr[i][1]+1):
      if j in like_number:
         count = count + 1
   print(count)

Submission status: Time Limit Exceeded

Solution code:
def Prime(x):
   if x == 2:
      return 1
   elif (x<2) or (x%2==0):
      return 0
   else:
      i = 3
      while i <= x**0.5:
         if x%i == 0:
            return 0
         i = i + 2
      return 1

Q = int(input())
l_r = []
for i in range(Q):
   l_r.append(list(map(int, input().split())))

like_Number = []

X_mem = []
X_mem_non = []
for l_r in l_r:
   l = l_r[0]
   r = l_r[1]
   count = 0
   for x in range(l, r+1):
      if x%2 == 1: # 奇数だけ
         if x in X_mem:
            count = count + 1
         elif (x in X_mem_non) == False:
            if Prime(x) == 1:
               if Prime((x+1)/2) == 1:
                  X_mem.append(x)
                  count = count + 1
               else:
                  X_mem_non.append(x)
            else:
               X_mem_non.append(x)

   like_Number.append(count)

for i in range(Q):
   print(like_Number[i])

Submission status: Time Limit Exceeded

Solution code:
def Prime(x):
   if x == 2:
      return 1
   elif (x<2) or (x%2==0):
      return 0
   else:
      i = 3
      while i <= x**0.5:
         if x%i == 0:
            return 0
         i = i + 2
      return 1

Q = int(input())
l_r = []
for i in range(Q):
   l_r.append(list(map(int, input().split())))

like_Number = []

for l_r in l_r:
   l = l_r[0]
   r = l_r[1]
   count = 0
   for x in range(l, r+1):
      if x%2 == 1: # 奇数だけ
         if Prime(x) == 1:
            if Prime((x+1)/2) == 1:
               count = count + 1
   like_Number.append(count)

for i in range(Q):
   print(like_Number[i])