无平方因子数即对于任意一个素数p,p^2都不会整除那个数,如,3,5,7,15=3*5都是无平方因子数,而20=4*5=2^2*5不是!
先找素数,然后用容斥原理,递归求解
描述
In mathematics, a square-free integer is one divisible by no perfect square, expect 1.Such as 10,but 12 is not because 12=4×3.
So the problem is very simple, give you an interval [n,m],can should calculate how many square-free numbers in this interval?
输入
Each line will consist of two integers n,m(0<n<=m<10^9),end by EOF.
输出......
阅读全文