Buggy python submission (verdict: Time Limit Exceeded):

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    LR.append(list(map(int,input().split())))
    l,r=LR[-1]
    L=l if l>L else L
    R=r if r>R else R

M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=set()
a=2
count=0
for a in range(2,M):
    if a in numlst:
        numlst.remove(a)
        if a:
            sosuulst.add(a)
        numLst=list(numlst)
        for i in numLst:
            if i%a==0:
                numlst.remove(i)
        if (a+1)//2 in sosuulst:
            count+=1
    if a>=3:
        lst[a]=count
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


Fixed submission:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Buggy python submission (verdict: Time Limit Exceeded):

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=set()
a=2
count=0
for a in range(2,M):
    if a in numlst:
        numlst.remove(a)
        if a:
            sosuulst.add(a)
        numLst=list(numlst)
        for i in numLst:
            if i%a==0:
                numlst.remove(i)
        if (a+1)//2 in sosuulst:
            count+=1
    if a>=3:
        lst[a]=count
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


Fixed submission:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Buggy python submission (verdict: Time Limit Exceeded):

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
a=2
while numlst:
    while not a in numlst:
        a+=1
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    numLst=list(numlst)
    for i in numLst:
        if i%a==0:
            numlst.remove(i)

sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


Fixed submission:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Buggy python submission (verdict: Time Limit Exceeded):

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
dellist=set()
a=2
while numlst:
    while not a in numlst:
        a+=1
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    dellist.clear()
    for i in numlst:
        if i%a==0:
            dellist.add(i)
    for i in dellist:
        numlst.remove(i)

sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


Fixed submission:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Buggy python submission (verdict: Time Limit Exceeded):

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
dellist=set()
while numlst:
    a=min(numlst)
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    dellist.clear()
    for i in numlst:
        if i%a==0:
            dellist.add(i)
    for i in dellist:
        numlst.remove(i)
sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


Fixed submission:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])

Buggy python submission (verdict: Time Limit Exceeded):

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])

M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


Fixed submission:

Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])