Squarefree number

Time Limit: 10000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1125    Accepted Submission(s): 274

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

题意很简单，就是然你判断一个数能不能被一个数的平方整除（注意这个数的范围是1~10^18）

以下转载于：

/*

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

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

10^18=10^6^2*10^6;

*/

下面是神龙的解题思路，我跳过了第三步；

/*

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

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

    否则 N=N/p

3.  消除N的小于 1000000的因子p后，若N=1 , 则Yes，转 5

4.  N必为 3种之一: 素数，素数的平方，两个不同素数之积。

   因此判断 N是否平方数，是平方数则No，不是则Yes

5. 结束 

*/

自己的体会：一个数可以写成n个素数的乘积的形式如n=p1^k1*p2^k2*p3^k3....*pn^kn当ki>=2时就是no了；对于pi<10^6所对应的ki是否>=2很容易判断；如果n存在大于10^6的素数的话，最多存在两个这样的素数，当这两个素数相等的时候就no了，其他情况都是yes；

1 #include
     
        2 #include
      
         3 #include
       
          4 #define nmax 1000001  5 int prime[nmax], plen;  6 void init() {
    7     memset(prime, -1, sizeof(prime));  8     int i, j;  9     for (i = 2; i < nmax; i++) {
   10         if (prime[i]) {
   11             for (j = i + i; j < nmax; j += i) {
   12                 prime[j] = 0; 13             } 14         } 15     } 16     for (i = 2, plen = 0; i < nmax; i++) {
   17         if (prime[i]) {
   18             prime[plen++] = i; 19         } 20     } 21 } 22 int solve(long long n) {
   23     int i; 24     for (i = 0; (i < plen) && (prime[i] < n); i++) {
   25         if (n % prime[i] == 0) {
   26             n /= prime[i]; 27             if (n % prime[i] == 0) {
   28                 return 0; 29             } 30         } 31     } 32     return 1; 33 } 34 int main() {
   35 36     init(); 37     int i, t, te, flag; 38     long long n; 39     scanf("%d", &t); 40         for (i = 1; i <= t; i++) {
   41             scanf("%I64d", &n); 42             flag = solve(n); 43             printf("Case %d: ", i); 44             if (flag) {
   45                 te = (int) (sqrt(n * 1.0)); 46                 if (((long long) (te)) * te == n) {
   47                     printf("No\n"); 48                 } else {
   49                     printf("Yes\n"); 50                 } 51             } else {
   52                 printf("No\n"); 53             } 54         } 55 56     return 0; 57 }