题目:

给出正整数n和m，区间[n,m]内的“无平方因子”的数有多少个？整数p无平方因子当且仅当不存在k > 1,使得p是k * k的倍数。1 <= n <= m <= 10 ^ 12,m - n <= 10 ^ 7

思路分析:

  分析最坏情况[1, 10 ^ 12],如果一个个判断的话，显然时间太大，就算如题意m - n最大值为10 ^ 7，那样也会超时，所以我们考虑其它方法，即筛选法，考虑这中方法时，我们要把题目中的条件做一下逆向转换，也就是说对于一个数p，如果其2p*p，3p*p存在与上述范围内，则他们就不是无平方因子，有没有发现这个和素数筛选法很想，Right，我们总结一下，他们都有一个条件，这个条件我们把它称为正条件，我们必须能够转化出逆条件，

1.这个逆条件以某些数为起始，这些起始数一定符合题目条件。

2.以这些起始数为基底，扩展出不符合的数，将其删除就可以。

3.也就是说拓展出的这些数就是题目所不要的对立面的数。如我们用无平方因子的数，拓展有平方因子的数。

4.用数学归纳法证明一片，看是否有错。

所以我们可以枚举数p的倍数，2 *p*p.....k *p *p，在进一步这些无平方因子的数必是素数，所以我们可以以素数为基底，拓展有平方因子的数。

#include 
    
     #include 
     
      #include 
      
       #define MAXN 100000000int vis[MAXN]; int main(){	int n,m;	while(scanf("%d%d",&n,&m) != EOF){		 int count = 0;	     int k = sqrt(m + 0.5);	     memset(vis,0,sizeof(vis));		 for(int i = 2; i <= k; i++){		 	for(int j =i * i; j <= m;j += i * i){		 		if(j >= n){			 		vis[j] = 1;			 		count++;		 		}			 }		 }		 printf("%d\n",m - n + 1 - count);	} 	return 0;}