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 custom/custom-post-content-inner.html %}

示例代码

#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;
}

{% include custom/custom-post-content-footer.md %}

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

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

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

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