【GESP】C++五级真题（数论-素数思想考点） luogu-P10720 [GESP202406 五级] 小杨的幸运数字

13
27
312
430

10
21
30

1#include <iostream>
2#include <cmath>
3
4int main() {
5    int n;
6    std::cin >> n;                       // 读入待检测的正整数个数
7
8    for (int i = 0; i < n; i++) {
9        int a;
10        std::cin >> a;                   // 读入当前待检测的正整数
11        int count = 0;                   // 记录不同质因子的个数
12        // 试除法枚举可能的质因子，只需到 sqrt(a)
13        for (int j = 2; j <= sqrt(a); j++) {
14            if (a % j == 0) {            // j 是 a 的一个质因子
15                count++;                 // 发现新的质因子
16            }
17            // 将 a 中所有 j 因子全部除掉，避免重复计数
18            while (a % j == 0) {
19                a /= j;
20            }
21            // 提前退出：已经超过两种质因子，必定不是幸运数字
22            if (count > 2) {
23                break;
24            }
25        }
26        // 若剩余 a>1，则剩下的 a 本身也是一个质因子
27        if (a > 1) {
28            count++;
29        }
30        // 恰好两种不同质因子则输出 1，否则输出 0
31        std::cout << (count == 2 ? 1 : 0) << std::endl;
32    }
33
34    return 0;
35}

1#include <iostream>
2#include <vector>
3
4// 标记数组：is_primes[i]==0 表示 i 是质数；==1 表示合数
5int is_primes[1000005];
6// 线性筛得到的质数表，后续用于试除
7std::vector<int> prime_nums;
8
9int main() {
10    int n;
11    std::cin >> n;
12    // 0 和 1 不是质数，先标记
13    is_primes[0] = is_primes[1] = 1;
14
15    // 线性筛（欧拉筛）预处理 1~1e6 的质数
16    for (int i = 2; i <= 1000000; i++) {
17        if (is_primes[i] == 0) {          // i 是质数，加入质数表
18            prime_nums.push_back(i);
19        }
20        // 用当前质数表筛掉合数
21        for (int num : prime_nums) {
22            long long x = 1LL * i * num;    // 计算合数
23            if (x > 1000000) {
24                break;                      // 超出范围，退出
25            }
26            is_primes[x] = 1;               // 标记为合数
27            if (i % num == 0) {
28                break;                      // 保证每个合数只被最小质因子筛一次
29            }
30        }
31    }
32
33    // 处理每个询问
34    for (int i = 0; i < n; i++) {
35        int a;
36        std::cin >> a;
37        int count = 0;                      // 记录不同质因子个数
38        // 用质数表试除，统计不同质因子
39        for (int j = 0; j < prime_nums.size(); j++) {
40            if (a % prime_nums[j] == 0) {   // 发现质因子
41                count++;
42            }
43            if (count > 2) {                // 提前剪枝
44                break;
45            }
46        }
47        // 恰好两种质因子输出 1，否则 0
48        std::cout << (count == 2 ? 1 : 0) << std::endl;
49    }
50
51    return 0;
52}
53}