Submission #67136375

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
def sieve(_n):
    count = [0]*(_n+1)
    pre=[]
    for i in range(2,_n+1):
        if count[i]:
            continue
        pre.append(i)
        for j in range(i,_n+1,i):
            count[j] += 1
    return pre
def cntP(L,R,P):
    cnt=[True]*(R-L+1)
    for p in P:
        if p*p>R:
            break
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import math

def sieve(_n):
    count = [0]*(_n+1)
    pre=[]
    for i in range(2,_n+1):
        if count[i]:
            continue
        pre.append(i)
        for j in range(i,_n+1,i):
            count[j] += 1
    return pre

def cntP(L,R,P):

    cnt=[True]*(R-L+1)

    for p in P:
        if p*p>R:
            break

        l=((L+p-1)//p)*p
        for m in range(max(l,p*p),R+1,p):
            cnt[m-L]=False

    if L==0:
        if R>=0: cnt[0]=False
        if R>=1: cnt[1]=False
    elif L==1:
        cnt[0] = False

    return sum(cnt)


L,R=map(int, input().split())


lim=int(math.isqrt(R))+1
pres=sieve(lim)

cnt=cntP(L+1,R,pres)


pp=0
K=int(math.log2(R))+1
for p in pres:
    if p*p>R:
        break
    val=p*p
    for k in range(2,K+1):
        if val>R:
            break
        if val>L:
            pp+= 1
        if val>R//p:
            break
        val*=p

print(1+cnt+pp)

Submission Info

Judge Result