Submission #10229763

---

Source Code Expand

Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)

for _ in range(Q):
    cnt = 0
    l, r = map(int, input().split())

    for x in range(l, r + 1):
        if prime[x] and prime[(x + 1) // 2]:
            cnt += 1

    print(cnt)

Submission Info

Judge Result