题目链接：
传送门
题目：
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;i
1000000) { 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; }