Submission #4075024

---

Source Code Expand

n = (int)(input())
s = []
t = []
for _ in range(n):
    a, b = (list)(map(int, input().split()))
    s.append(a)
    t.append(b)
mi = min(s)
ma = max(t)


def primeList(N):
    max = int(N//2)+5
    seachList = [i for i in range(2, N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


def prime(s, t):
    primes = primeList(t)
    l = [0]*(t+1)
    c = 0
    s = 0
    for i in range(s, t+1):
        if i in primes and (i+1)//2 in primes:
            c += 1
        l[i] = c
    return l


primes = prime(mi, ma)
for i in range(n):
    print(primes[t[i]] - primes[s[i]-1])

Submission Info

Judge Result