HDU 3826 Squarefree number （素数）

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. 1 <= T <= 20
2. 2 <= 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


AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int maxn = 1e6+10;

bool visit[maxn];
int prime[maxn];
int tot;
LL n;
void getprime()
{
tot=0;
memset(visit,0,sizeof(visit));
for(int i=2; i<maxn; i++)
{
if(!visit[i])
{
prime[tot++]=i;
for(int j=i+i; j<maxn; j+=i)
visit[j]=1;
}
}
}

bool solve()
{
for(int i=0; i<tot; i++)
{
if(n%prime[i]==0)
{
n/=prime[i];
if(n%prime[i]==0)
return false;
}
}
if(n>=1e6)
{
LL tmp = sqrt(n) + 0.5;
if(tmp*tmp==n)
return false;
}
return true;
}

int main()
{
getprime();
int T;
cin>>T;
for(int ti=1; ti<=T; ti++)
{
cin>>n;
cout<<"Case "<<ti<<": ";
cout<<(solve()?"Yes":"No")<<endl;
}
return 0;
}