#include<stdio.h> #include<string.h> #include<math.h> #define nmax 1000001 int prime[nmax], plen; void init() { memset(prime, -1, sizeof(prime)); int i, j; for (i = 2; i < nmax; i++) { if (prime[i]) { for (j = i + i; j < nmax; j += i) { prime[j] = 0; } } } for (i = 2, plen = 0; i < nmax; i++) { if (prime[i]) { prime[plen++] = i; } } } int solve(long long n) { int i; for (i = 0; (i < plen) && (prime[i] < n); i++) { if (n % prime[i] == 0) { n /= prime[i]; if (n % prime[i] == 0) { return 0; } } } return 1; } int main() { #ifndef ONLINE_JUDGE freopen("t.txt", "r", stdin); #endif init(); int i, t, te, flag; long long n; while (scanf("%d", &t) != EOF) { for (i = 1; i <= t; i++) { scanf("%I64d", &n); flag = solve(n); printf("Case %d: ", i); if (flag) { te = (int) (sqrt(n * 1.0)); if (((long long) (te)) * te == n) { printf("No\n"); } else { printf("Yes\n"); } } else { printf("No\n"); } } } return 0; }
以下转载于:
http://hi.baidu.com/304467594/blog/item/f02407ea9eeecac62f2e2136.html
/*
要判断给定的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. 结束
*/
#include<stdio.h> #include<string.h> #include<math.h> #define nmax 1000001 int prime[nmax], plen; void init() { memset(prime, -1, sizeof(prime)); int i, j; for (i = 2; i < nmax; i++) { if (prime[i]) { for (j = i + i; j < nmax; j += i) { prime[j] = 0; } } } for (i = 2, plen = 0; i < nmax; i++) { if (prime[i]) { prime[plen++] = i; } } } int solve(long long n) { int i; for (i = 0; (i < plen) && (prime[i] < n); i++) { if (n % prime[i] == 0) { n /= prime[i]; if (n % prime[i] == 0) { return 0; } } } return 1; } int main() { #ifndef ONLINE_JUDGE freopen("t.txt", "r", stdin); #endif init(); int i, t, te, flag; long long n; while (scanf("%d", &t) != EOF) { for (i = 1; i <= t; i++) { scanf("%I64d", &n); flag = solve(n); printf("Case %d: ", i); if (flag) { te = (int) (sqrt(n * 1.0)); if (((long long) (te)) * te == n) { printf("No\n"); } else { printf("Yes\n"); } } else { printf("No\n"); } } } return 0; }