HDU 3826 Squarefree number （素数）

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 Specification1 <= T <= 202 <= N <= 10^18

Output

For each test case, output the case number first. Then output “Yes” if N is squarefree, “No” otherwise.

Sample Input

23075

Sample Output

Case 1: YesCase 2: No

题意

判断一个数是否是“无平方数”（是这么翻译么？）

思路

显然 1018

考虑对 n

筛选完 106 以下的所有质因子以后，如果 n>106 ，则说明它最多含有两个 106

AC 代码

#includeusing 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=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 "<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。