要判断给定的n(2<=n<=10^18)是不是squarefree number；

因为给定的数最大达到10^18，所以直接暴力肯定是杯具的TLE；

我们知道  N必为 3种之一: 素数，素数的平方，两个不同素数之积。

10^18=10^6^3;那么我们求质数就只要求到10^6就可以，因为大于10^6就只能是平方次方，不可能是立方，因此可以用开方来判断；

假如我们求质数小于10^6，那么可能这个数是一个数的立方，或者是一个质数的平方乘以一个数，但不能开方，但又不能被前面的质数相除，因此会造成不是squarefree number的假象。

实现思路：

1. 计算1000000以下 素数，存于 num[ ]

2. 计算N的 小于1000000的因子p，如果有平方因子，则No，转 5

    否则 N=N/p

3.  消除N的小于 1000000的因子p后，判断是否还可以开方；

#include
     
       #include
      
        #include
       
         int hash[500024]={
    0}; int prime( int num[] ) {
    for( int i=3;i<=1000;i+=2 )     {
    if( hash[i/2] ) continue; int x=i<<1; for( int j=i*i; j<=1000000; j+=x )             hash[j/2]=1;        } int count=0;     num[++count]=2; for( int i=1;i<=500000;i++ )     {
    if( hash[i]==0 )          num[++count]=( i<<1 )+1;         }    return count; } bool  judge( int num[], int count , long long  number ) {
    long long t=( long long )sqrt( number ) ; for( int i=1;i<=count; i++ )     {
    if( number==1 ) break; if( 0==(number%num[i]) )          {
                 number/=num[i]; if( number%num[i]==0 )  return true;              }          } if( number!=1 )     {
             t=( long long  )sqrt( number ) ; if( (t*t)==number )  return true;          } return false;     } int main( ) {
    int T,num[78550]; int count = prime( num );     scanf( "%d",&T ); for( int i=1;i<=T; i++ )     {
    long long number;         scanf( "%I64d",&number );         printf( "Case %d: ",i ); bool t=judge( num,count,number );         printf( t?"No\n":"Yes\n" );     } return 0;    }