【GESP】C++四级练习 luogu-B3939 [GESP样题 四级] 绝对素数

GESP C++四级练习，函数应用练习，难度⭐⭐★☆☆。

luogu-B3939 [GESP样题 四级] 绝对素数

题目要求

题目描述

如果一个两位数是素数，且它的数字位置经过对换后仍为素数，则称为绝对素数，例如 $13$。给定两个正整数 $A, B$，请求出大于等于 $A$、小于等于 $B$ 的所有绝对素数。

输入格式

输入 $1$ 行，包含两个正整数 $A$ 和 $B$。保证 $10<A<B<100$。

输出格式

若干行，每行一个绝对素数，从小到大输出。

输入输出样例 #1

输入 #1

11 20

输出 #1

11
13
17

---

题目分析

解题思路

本题的解题思路如下：

1. 函数设计
   • 需要两个关键函数:
     1. is_prime_number: 判断一个数是否为素数
     2. is_abs_prime_number: 判断一个数是否为绝对素数
   • 函数参数和返回值:
     • 入参都是整型数字
     • 返回布尔值表示判断结果
2. 素数判断函数实现
   • 实现思路：从2到$\sqrt{n}$遍历，检查是否有因子
   • 时间复杂度：$O(\sqrt{n})$
   • 空间复杂度：$O(1)$

   bool is_prime_number(int num) {
       // 从2到sqrt(num)遍历判断
       for (int i = 2; i * i <= num; i++) {
           if (num % i == 0) return false;
       }
       return true;
   }
   

3. 绝对素数判断函数实现
   • 实现思路：先判断数字本身是否为素数，再判断数字位置对换后的新数是否为素数
   • 时间复杂度：$O(\sqrt{n})$
   • 空间复杂度：$O(1)$

   bool is_abs_prime_number(int num) {
       // 原数必须是素数
       if (!is_prime_number(num)) return false;
       // 数位互换: 13 -> 31
       int swap_num = (num % 10) * 10 + num / 10;
       // 互换后也必须是素数
       return is_prime_number(swap_num);
   }
   

4. 主程序实现

   int main() {
       int A, B;
       cin >> A >> B;
       // 遍历区间[A,B]
       for (int i = A; i <= B; i++) {
           if (is_abs_prime_number(i)) {
               cout << i << "\n";
           }
       }
       return 0;
   }
   

5. 算法分析
   • 时间复杂度：$O(n\sqrt{n})$
     • 区间长度为n
     • 每个数判断素数需要$O(\sqrt{n})$
   • 空间复杂度：$O(1)$
     • 只使用常数级别变量

---

示例代码

#include <iostream>

/**
 * 判断一个数是否为素数
 * @param num 待判断的数字
 * @return true表示是素数，false表示不是素数
 */
bool is_prime_number(int num) {
    bool flag = true;
    // 从2到sqrt(num)遍历，检查是否有因子
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

/**
 * 判断一个数是否为绝对素数
 * 绝对素数：两位数本身是素数，且数字位置对换后仍为素数
 * @param num 待判断的数字
 * @return true表示是绝对素数，false表示不是绝对素数
 */
bool is_abs_prime_number(int num) {
    // 先判断数字本身是否为素数
    bool flag = is_prime_number(num);

    if (flag) {
        // 计算数字位置对换后的新数
        // 例如：13 -> 31
        // num % 10得到个位，乘10后变为十位
        // num / 10得到十位，变为个位
        int alter_num = num % 10 * 10 + num / 10;
        // 判断对换后的数是否为素数
        flag = is_prime_number(alter_num);
    } 
    return flag;
}

int main() {
    // 定义区间范围变量
    int A,B;
    // 读入区间范围
    std::cin >> A >> B;
    // 遍历区间内的每个数
    for (int i = A; i <= B; i++) {
        // 如果是绝对素数则输出
        if(is_abs_prime_number(i)) {
            std::cout << i << "\n";
        }
    }
    return 0;
}

---

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

GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。

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

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

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

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

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