#エラトステネスの篩 def Sieve_of_Eratosthenes(N,mode=False): """Nまでのエラトステネスの篩を実行 N:自然数 mode:False->素数のリスト,True->素数かどうかのリスト (False->[2,3,5,...],True->[0,0,1,1,0,1,...]) """ if N==0: return [0] T=[1]*(N+1) T[0]=T[1]=0 for x in range(4,N+1,2): T[x]=0 for x in range(9,N+1,3): T[x]=0 a=5 Flag=0 while a*a<=N: if T[a]: b=a*a c=2*a while b<=N: T[b]=0 b+=c a+=2+2*Flag Flag^=1 if mode: return T else: return [k for k in range(N+1) if T[k]] #================================================== N=int(input()) M=0 while (M+1)*(M+1)<=N: M+=1 Y=[0]*(N+1); Y[1]=1 A=list(range(N+1)) for p in Sieve_of_Eratosthenes(M): if p*p>N: break q=s=p*p Y[q]=1 while q<=N: r=q while r<=N: A[r]//=s r+=q q*=p*p for i in range(1,N+1): Y[i]+=Y[i-1] K=0 for i in range(1,N+1): K+=Y[N//A[i]] print(K)