建站网站教程视频/淘宝运营培训机构

hdu 3826 Squarefree number（数论，素数）（c++）

题目链接： Squarefree number
题目大意： 在数学中，无平方数是一个可以被除以1以外的任何平方都不被整除的数。例如，10是无平方的，而18没有，因为它可以被9 = 3 ^ 2整除。现在，您需要确定一个整数是否为无平方的。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>using namespace std;
typedef long long ll;int is[1000005];
int cnt = 0;
int prime[1000000];
int t;
ll n;void isprime(){memset(is, 0, sizeof(is));for(int i = 2; i <= 1000000; i++){if(is[i] == 0){prime[cnt++] = i;for(int j = 2 * i; j <= 1000000; j += i){is[j] = 1;}}}
}bool slove(){for(int i = 0; i < cnt; i++){if(n % prime[i] == 0){n = n / prime[i];if(n % prime[i] == 0){return false;}}}if(n >= 10e6){ll tmp = sqrt(n);if(tmp*tmp==n)return false;}return true;
}int main()
{isprime();cin >> t;for(int i = 1; i <= t; i++){cin >> n;if(slove()){cout << "Case " << i <<": Yes" << endl;}else{cout << "Case " << i <<": No" << endl;}}return 0;
}