T-primes (数论)_用c++判断一个数是否只有3个因数

T-primes

题目链接

大致题意:

判断一个数是否仅含有3个因子

---

解题思路:

1. 我们考虑有奇数个因数的整数的特点：显然它是一个完全平方数 。而判断完全平方数，只需要判断sqrt(x)取整的平方是否等于x即可

2. 接下来考虑有三个因数的整数的特点：易知sqrt(x)不可再分解了，也就是质数，因此我们只需要将[1,sqrt(x)]范围内的所有质数筛出来即可

   重点:质数的平方包含三个因子

---

AC代码:

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define debug(a) cout << #a << " = " << a << endl;
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, m;
int prime[N], cnt, vis[N];
void get_primes(int n)
{
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prime[cnt++] = i;
		for (int j = 0; i * prime[j] <= n; j++) {
			vis[prime[j] * i] = true;
			if (i % prime[j] == 0) break;
		}
	}
}
int main(void)
{
	get_primes(N - 5);
	cin >> n;
	while (n--) {
		ll x; cin >> x;
		ll op = sqrt(x);
		if (op * op == x && !vis[op] && x > 1)puts("YES");
		else puts("NO");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---