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

GESP C++ 2024年6月五级真题，数论-素数思想考点，难度⭐⭐★☆☆，属于五级真题中比较简单的。洛谷难度等级普及−

luogu-P10720 [GESP202406 五级] 小杨的幸运数字

题目要求

题目描述

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，$12=2\times 2\times 3$ 的质因子有 $2,3$，恰好为两种不同的质因子，因此 $12$ 是幸运数字，而 $30=2\times3\times5$ 的质因子有 $2,3,5$，不符合要求，不为幸运数字。

小杨现在有 $n$ 个正整数，他想知道每个正整数是否是他的幸运数字。

输入格式

第一行包含一个正整数 $n$，代表正整数个数。

之后 $n$ 行，每行一个正整数。

输出格式

输出 $n$ 行，对于每个正整数，如果是幸运数字，输出 $1$，否则输出 $0$。

输入输出样例 #1

输入 #1

3
7
12
30

输出 #1

0
1
0

说明/提示

样例解释

$7$ 的质因子有 $7$，只有一种。

$12$ 的质因子有 $2,3$，恰好有两种。

$30$ 的质因子有 $2,3,5$，有三种。

数据范围

子任务编号	数据点占比	$n$	正整数值域
$1$	$40\%$	$\leq 100$	$\leq 10^5$
$2$	$60\%$	$\leq 10^4$	$\leq 10^6$

对于全部数据，保证有 $1\leq n\leq 10^4$，每个正整数 $a_i$ 满足 $2\leq a_i\leq 10^6$。

---

题目分析

解题思路

1. 读入 $n$ 与 $n$ 个正整数。
2. 对每个数 $a$：
   • 初始化计数器 count = 0。
   • 从 $2$ 开始试除到 $\lfloor\sqrt{a}\rfloor$：
     – 若 $j\mid a$，说明 $j$ 是一个新质因子，count++。
     – 把 $a$ 中所有 $j$ 因子全部除掉，避免重复。
     – 一旦 count > 2 立即 break，提前剪枝。
   • 若最终剩余 $a>1$，则剩余部分本身也是质因子，count++。
3. 判断 count == 2 输出 $1$，否则输出 $0$。

复杂度
单次分解最坏 $O(\sqrt{a_i})$，$n\le 10^4,\ a_i\le 10^6$ 时总运算量约 $10^4\times 10^3=10^7$ 级，可轻松通过。
空间仅若干变量，$O(1)$。

该做法代码极短，无需预处理，在五级数据范围内已足够高效；若值域再大，可改为“埃氏筛+质数表试除”进一步加速（不做展开，详见示例代码）。

---

示例代码

方法一、直接法

#include <iostream>
#include <cmath>

int main() {
    int n;
    std::cin >> n;                       // 读入待检测的正整数个数

    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;                   // 读入当前待检测的正整数
        int count = 0;                   // 记录不同质因子的个数
        // 试除法枚举可能的质因子，只需到 sqrt(a)
        for (int j = 2; j <= sqrt(a); j++) {
            if (a % j == 0) {            // j 是 a 的一个质因子
                count++;                 // 发现新的质因子
            }
            // 将 a 中所有 j 因子全部除掉，避免重复计数
            while (a % j == 0) {
                a /= j;
            }
            // 提前退出：已经超过两种质因子，必定不是幸运数字
            if (count > 2) {
                break;
            }
        }
        // 若剩余 a>1，则剩下的 a 本身也是一个质因子
        if (a > 1) {
            count++;
        }
        // 恰好两种不同质因子则输出 1，否则输出 0
        std::cout << (count == 2 ? 1 : 0) << std::endl;
    }

    return 0;
}

方法二、线性筛法（相对复杂）

#include <iostream>
#include <vector>

// 标记数组：is_primes[i]==0 表示 i 是质数；==1 表示合数
int is_primes[1000005];
// 线性筛得到的质数表，后续用于试除
std::vector<int> prime_nums;

int main() {
    int n;
    std::cin >> n;
    // 0 和 1 不是质数，先标记
    is_primes[0] = is_primes[1] = 1;

    // 线性筛（欧拉筛）预处理 1~1e6 的质数
    for (int i = 2; i <= 1000000; i++) {
        if (is_primes[i] == 0) {          // i 是质数，加入质数表
            prime_nums.push_back(i);
        }
        // 用当前质数表筛掉合数
        for (int num : prime_nums) {
            long long x = 1LL * i * num;    // 计算合数
            if (x > 1000000) {
                break;                      // 超出范围，退出
            }
            is_primes[x] = 1;               // 标记为合数
            if (i % num == 0) {
                break;                      // 保证每个合数只被最小质因子筛一次
            }
        }
    }

    // 处理每个询问
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        int count = 0;                      // 记录不同质因子个数
        // 用质数表试除，统计不同质因子
        for (int j = 0; j < prime_nums.size(); j++) {
            if (a % prime_nums[j] == 0) {   // 发现质因子
                count++;
            }
            if (count > 2) {                // 提前剪枝
                break;
            }
        }
        // 恰好两种质因子输出 1，否则 0
        std::cout << (count == 2 ? 1 : 0) << std::endl;
    }

    return 0;
}
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号