Problem Description In mathematics, a squarefree number is one which is divisible by no perfect squares, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 3^2. Now you need to determine whether an integer is squarefree or not.
Input The first line contains an integer T indicating the number of test cases. For each test case, there is a single line contains an integer N.
Technical Specification
1 <= T <= 202 <= N <= 10^18
Output For each test case, output the case number first. Then output “Yes” if N is squarefree, “No” otherwise.
Sample Input 2 30 75
Sample Output Case 1: Yes Case 2: No
题解：
参考大神题解[题解](http://blog.csdn.net/acdreamers/article/details/8678651)
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn=
1000000;
long long prime[maxn+
5];
long long n;
void getPrime()
{
memset(prime,
0,
sizeof(prime));
for(LL i=
2;i<=maxn;i++)
{
if(!prime[i])
{
prime[++prime[
0]]=i;
}
for(LL j=
1;j<=prime[
0]&&prime[j]<=maxn/i;j++)
{
prime[prime[j]*i]=
1;
if(i%prime[j]==
0)
break;
}
}
}
bool Test()
{
int i;
for(i=
1;i<prime[
0]&&prime[i]<n;i++)
{
if(n%prime[i]==
0)
{
n/=prime[i];
if(n%prime[i]==
0)
{
return false;
}
}
}
return true;
}
int main()
{
int T;
cin>>T;
int kn=
1;
getPrime();
while(T--)
{
scanf(
"%I64d",&n);
bool flag=
0;
if(!Test())
flag=
true;
if (!flag)
{
double temp =
sqrt(n *
1.0);
if ((
int)(temp +
0.5) == temp) flag =
1;
}
if(flag)
printf(
"Case %d: No\n",kn++);
else printf(
"Case %d: Yes\n",kn++);
}
return 0;
}
