題目鏈接：

傳送門

題目：

Squarefree number

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2047 Accepted Submission(s): 540


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. 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

Author hanshuai
Source The 6th Central China Invitational Programming Contest and 9th Wuhan University Programming Contest Final
Recommend lcy | We have carefully selected several similar problems for you: 3823 3818 3819 1060 3822

因為數的范圍為10的18次方，那麼它的因子必須是小於10的6次方的，則n*n*n>10的18次方，所以打一個1000000的素數表，
首先是素數表，用篩法打素數表。復雜度為O(ologn)，應該是目前來說最快的吧。。
如果一個數在整除素數1000000後任然大於10的6次方的話，則將其開方後再乘。詳情參見小白178面。

有個非常詳細的講解的。

傳送門 講的非常好。。

我的代碼如下：

#include
#include
#include
const int maxn=80000+10;
const int  n=1000000;
int prime[maxn],vis[n];
__int64 N;
int  pos;
int init()
{
    int c=0;
    int m;
    memset(vis,0,sizeof(vis));
    m=sqrt(n+0.5);
    for(int i=2;i<=m;i++)
    {
       if(!vis[i])
       {
           for(int j=i*i;j<=n;j+=i)
              vis[j]=1;
       }
    }
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
            prime[c++]=i;
    }
    return c;
}

int judge()
{
   for(int i=0;i1000000)
        {
            x=(int)sqrt(double(N));
            if(x*x==N)
                ok=0;
        }
        if(ok)
            printf("Case %d: Yes\n",cas++);
        else
            printf("Case %d: No\n",cas++);
    }
    return 0;
}