【题目描述】

给出正整数n，m，区间[n,m]内的无平方因子数有多少个?

整数p无平方因子，当且仅当不存在k>1,使p是k^2的倍数，1<=n<=m<=10^12,m-n<=10^7

【输入格式】

两个整数n，m

【输出格式】

[n,m]间的无平方因子数的个数

【样例输入】

1 5

【样例输出】

4

【提示】

在此键入。

【来源】

刘汝佳《入门经典》

 

题意 ： 对于所给区间，询问没有平方因子的数有多少个？

思路分析 ： 这个题的思想类似区间素数筛，首先将 2 到 sqrt(m)的素数全部找到，然后将所求区间内是素数平方倍数的数全部去掉，用一个数组去保存，很关键的一点是 区间的长度时不超过 1e7 的，因此只需要开一个这样长度的数组即可，计算的时候离散即可。

素数定理 ： cnt(x) 约等于 x/(lnx) 。

代码示例 ：

#define ll long longconst int maxn = 1e6+5;const int mm = 1e7+5;const int mod = 1e9+7;const double eps = 1e-9;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;ll n, m;bool pt[maxn];bool f[mm];void init(){    memset(pt, true, sizeof(pt));    for(ll i = 2; i <= sqrt(m); i++){        if(pt[i]){            for(ll j = i+i; j <= sqrt(m); j += i){                pt[j] = false;            }        }    }    //pt[1] = false;    }int main() {    freopen("non.in", "r", stdin);    freopen("non.out", "w", stdout);        cin >> n >> m;    if (n > m) swap(n, m);    init();        memset(f, true, sizeof(f));    for(ll i = 2; i <= sqrt(m); i++){        if (pt[i]){            for(ll j = i*i*((n+i*i-1)/(i*i)); j <= m; j += i*i){                f[j-n] = false; // 离散            }        }    }    int cnt = 0;    for(ll i = 0; i <= m-n; i++) if (f[i]) cnt++;    printf("%d\n", cnt);     return 0;}