ZJ a121. 質數又來囉

ZJ a121

b<=100000000
n = b**0.5
nlist:標記0~n是否為質數
plist:質數清單

輸入a,b

ablist：標示是否為質數，逐一利用plist檢查a…b是否為質數
ans = sum(ablist)

code

AC (8.3s, 3.5MB)

n=10000
nlist = [0,0,1]
for i in range(n//2+1):
    nlist += [1,0]
plist = [2]
for i in range(3,n,2):
    if nlist[i]:
        plist.append(i)
    for pi in plist:
        if pi*i>n: break
        nlist[pi*i] = 0
        if i % pi ==0: break


while True:
    try:
        a,b = map(int,input().split())
        if a==1: a=2
        if a>b:
            ans = 0
        else:
            ablist = [1]*(b-a+1)
            for x in range(a,b+1):
                for p in plist:
                    if p > x**0.5:break
                    if x % p == 0:
                        ablist[x-a] = 0
                        break
            ans = sum(ablist)                    
        print(ans)

    except EOFError:
        break