Submission #10230051

---

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)
primeSum = [0] * (MAX + 1)
for x in range(1, MAX + 1):
    primeSum[x] = primeSum[x - 1]
    if prime[x] and prime[(x + 1) // 2]:
        primeSum[x] += 1
        

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

    print(primeSum[r] - primeSum[l - 1])

Submission Info

Judge Result