记录编号	192187	评测结果	AAAAAAAAAA
题目名称	无平方因子数	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.487 s
提交时间	2015-10-09 21:49:05	内存使用	9.85 MiB

#include<cstdio>
#include<deque>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;
deque<LL> P;
LL N,M,ans=0;
bool H[10000100]={0};
void Prime(LL n)
{
	bool visit[1000010]={0};
	LL m=sqrt(n+0.5);
	for(LL i=2;i<=m;i++)
	{
		if(visit[i]==0)
		{
			P.push_back(i);
			for(LL j=i*i;j<=m;j+=i)
				visit[j]=1;
		}
	}
}
int main()
{
	freopen("non.in","r",stdin);
	freopen("non.out","w",stdout);
	scanf("%lld%lld",&N,&M);
	Prime(M);
	for(int i=0;i<P.size();i++)
	{
		LL now=P[i]*P[i];
		for(LL j=N/now*now;j<=M;j+=P[i]*P[i]) if(j>=N) H[j-N]=1;
	}
	for(int i=0;i<=M-N;i++) if(H[i]==0) ans++;
	printf("%d",ans);
	return 0;
}