题解 | 几乎是质数

import sys
n=int(input())
count=[0]*(n+1)#记录i的质因子数
for i in range(2,n+1):
    if count[i]==0:
    #如果i的质因子数为0，那么i为质数，则i为其倍数的质因子，所以其倍数的质因子数都要加1
        for j in range(i,n+1,i):
        #step为i每次加i，即为其倍数
            count[j]+=1
res=0
for i in range(2,n+1):
    #如果其质因子数等于2，则认定为几乎质数
    if count[i]==2:
        res+=1
print(res)