Squarefree number
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1476 Accepted Submission(s): 390
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.
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
算法分析：
对于2-10^18的任意一个数 都能转化成如下的形式 
……等等 a，b，c，d都是质数
然后
情况1 将输入的num 先从 2-10^6中的质数进行相除，有一个质数能连出两次以上 就输出no
情况2 如果能整除 num=num/i 然后 如果 相除后num==1 输出yes
进行完一二操作后 本题中剩下的num这个数 （因为不存在1-10^6的质数） 最多只有两个质数
情况3 只有两种结果 两个10^6-10^9 的质数相乘 或者只有一个质数 在10^6-10^18次方之间。 这样只要判断第一种结果是否是两个相同质数相乘的情况了~~
post code：
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 1100000
#define MIN 0.00001
int a[MAX];
int b[500000],flag;
int select() //筛选法求素数
{
int i,j=1;
memset( a, 0, sizeof(a) );
a[1]=1;
for( i=2; i*i<MAX; i++ )
{
if( a[i]==0 )for( j=2*i; j<MAX; j+=i )
{
a[j]=1;
}
}
j=1;
for( i=2; i<MAX ;i++)
{
if(a[i]==0){b[j]=i;j++;}
}
return j;
}
void issquare( double num ) //判断开方是否为整数
{
double a;
a=sqrt(num);
if( a-floor(a)<MIN )flag=1;
}
int main()
{
int i,len,x,sum,ji=0;
__int64 num;
len=select();
scanf("%d",&x);
while(x--)
{
ji++;
flag=0;
scanf("%I64d",&num);
for( i=1; i<len; i++)
{
sum=0;
while( num%b[i]==0 )
{
num/=b[i];
sum++;
}
if( sum>=2 ){
flag=1;
break;
}
}
if(flag==1){printf("Case %d: No\n",ji);continue;} //情况1
if(num==1){printf("Case %d: Yes\n",ji);continue;} //情况2
issquare((double) num); //情况3
if(flag==1)printf("Case %d: No\n",ji);
else printf("Case %d: Yes\n",ji);
}
}