回文质数

自己的思路分析，以防自己忘记

题目描述

因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a, b](5 ≤ a < b ≤ 100,000,000)间的所有回文质数。

输入格式

第一行输入两个正整数 a 和 b。

输出格式

输出一个回文质数的列表，一行一个。

题目来源于洛谷 回文质数 Prime Palindromes

我的解题思路

通过以上的题目信息我们可以得到一个基本的思路
1.判断某个数是否是质数
2.判断某个数是否是回文数
3.这个数是否同时满足以上两个条件

函数设计

判断是否为质数

在设计函数之前，我们要明确质数的概念。
质数:指大于1的自然数中，除了1和它本身以外不再有其他因数的数。
我们可以有以下的设计思路:

• 我们可以通过遍历[2,n)，再将遍历的某个数与n相除,若没有余数说明他们能够整除，即不满足质数的条件

于是我们便有以下的代码

1
2
3
4
5
6
7
8
9
10
11
12

bool is_prime(int num)
{
    
    for (int i = 2; i < num; ++i)
    {
        if (num % i == 0)
            return false;
        
    }

    return true;
}

大O记法是O(N)

判断是否为回文

首先我们要明确什么是回文
回文:正读和反读都一样的序列

数字其实并不是很好弄，如果它能够在数组中，然后通过索引判断是否相等就好了。这样，我们便得到了第一种设计思路：

• 通过两侧的索引来判断是否都相等
• 循环的条件:左索引小于右索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool is_huiwen(int num)
{
    string str = to_string(num);

    int left = 0;
    int right = str.length() - 1;

    while (left < right)
    {
        if (str[left] != str[right])
        {
            return false;
        }
        ++left;
        --right;
    }

    return true;
}

有N个数据，则需要N/2步
大O记法是O(N)

设计主函数

主函数只需要接受传入的范围再进行遍历，并且判断条件即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int main()
{
    int num1, num2;
    cin >> num1 >> num2;

    for (int i = num1; i <= num2; ++i)
    {
        bool isprime = is_prime(i);
        bool ishuiwen = is_huiwen(i);
        if (isprime == true && ishuiwen == true)
        {
            cout << i << endl;
        }
    }

    return 0;
}

优化

如果我们将代码提交到洛谷官网，你会发现总有几个会显示TLE(Time Limit Exceeded),这表示我们设计的代码在效率上有着较大的问题，那么我们如何去提高代码的运行效率呢？

优化判断质数函数

通过质数的定义我们可以知道，质数只能和它自己与1相整除。
那么我就可以知道，偶数(除2以外)一定不是质数，因为他们都能和2相整除，就不需要一个一个遍历了，我们只需要检查奇数,大大提高了代码的判断效率。

1
2
3
4
5
6
7
8
9
10
11
12
13

bool is_prime(int num)
{
    if (num % 2 == 0)
        return false;

    for (int i = 3; i <= num; i = i + 2)
    {
        if (num % i == 0)
            return false;
    }

    return true;
}

有N个数据，则需要N/2步
大O记法为O(N)

如果我们还想进一步优化，让代码变得更快，我们还需要理解下面的概念。

假设 n 是一个合数（非质数），那么它至少有一个因数对 (a,b) 使得 a×b=n。在这个因数对中，至少有一个因数 a 或 b 必须小于或等于(\sqrt{n}) 。这是因为如果 a 和 b 都大于(\sqrt{n})，那么它们的乘积 a×b 将大于 n，这与 a×b=n 矛盾。

这个原理允许我们减少检查的范围，从而提高判断质数的效率。我们只需要检查从 2 到(\sqrt{n})的所有整数，看它们是否能整除 n。如果都不能整除，那么 n 就是质数。

那我们的最终代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool is_prime(int num)
{
    if (num % 2 == 0)
        return false;
else
    {
        for (int i = 3; i <= sqrt(num); i = i + 2)
        {
            if (num % i == 0)
                return false;
        }

        return true;
    }
}

大O记法O((\sqrt{n})),效率大大提高

优化判断回文函数

我们最直接的想到的就是通过字符串数组来判断是否相等。其实，我们也可以通过数学运算来判断是否为回文数。
原理: 通过数学运算将数字反转，如果和原来的数字相等，即为回文数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

bool isPalindrome(int num) {
    if (num < 0) {
        return false; 
    }
    int reversed = 0;
    int original = num;

    while (num > 0) {
        reversed = reversed * 10 + num % 10; 
        num /= 10;
    }

    return original == reversed; 
}

具体解释：

1. 循环条件：while (num > 0) 确保循环在原数 num 大于 0 时继续执行。当 num 变为 0 时，循环结束。
2. 提取最后一位数字：num % 10 用于提取 num 的最后一位数字。例如，如果 num 是 1234，那么 num % 10 的结果是 4。
3. 构建反转数：reversed = reversed * 10 + num % 10 这一步是将提取的最后一位数字添加到 reversed 的末尾。具体来说：
   • reversed * 10 将 reversed 的所有位数向左移动一位，为新数字腾出空间。
   • + num % 10 将提取的最后一位数字添加到 reversed 的末尾。
4. 更新原数：num /= 10 用于移除 num 的最后一位数字。例如，如果 num 是 1234，那么 num /= 10 后，num 变为 123。