20.3 嵌套循环与数论问题

“数论问题常常需要我们检查数字的特殊性质，”我解释道，”比如质数判定、回文数判断等，这些都可以通过嵌套循环来实现。”

20.3.1 统计质数

题目描述：统计a~b(1≤a<b≤100,000)之间有多少质数。

样例输入：

10 20

样例输出：

4

代码实现：

#include <iostream>
using namespace std;

int main() {
    int a, b, cnt=0;  // a和b是范围边界，cnt用于计数质数个数
    bool f;           // 布尔变量f用来标记当前数是否为质数
    cin >> a >> b;    // 读入范围边界
    
    // 外循环：遍历a到b的每个数
    for(int i=a; i<=b; i++) {
        f = true;     // 初始假设i是质数
        
        // 特殊情况处理：小于2的数不是质数
        if(i < 2) f = false;
        
        // 内循环：检查i是否能被2到sqrt(i)的数整除
        // 只需检查到sqrt(i)，因为如果i不是质数，至少有一个因子小于等于sqrt(i)
        for(int j=2; j*j<=i; j++) {
            if(i % j == 0) {  // 如果i能被j整除
                f = false;    // 则i不是质数
                break;        // 找到一个因子就可以确定非质数，立即退出循环
            }
        }
        
        // 如果i是质数，计数器加1
        if(f) cnt++;
    }
    cout << cnt;  // 输出质数总数
    return 0;
}

思考：

• 外循环(i)遍历从a到b的每个数
• 内循环(j)检查i是否能被2到sqrt(i)的任何数整除
• 使用布尔变量f标记当前数是否为质数
• 优化：只需要检查到sqrt(i)，如果i有约数，其中一个一定小于等于sqrt(i)
• 进一步优化：使用break提前结束内循环，一旦发现i不是质数

20.3.2 统计回文数

题目描述：统计a~b(1≤a<b≤100,000)之间回文数的个数。回文数是指从左向右读和从右向左读都一样的数，如121、1221等。

样例输入：

10 100

样例输出：

9

代码实现：

#include <iostream>
using namespace std;

int main() {
    int a, b, cnt=0;  // a和b是范围边界，cnt用于计数回文数个数
    cin >> a >> b;    // 读入范围边界
    
    // 外循环：遍历a到b的每个数
    for(int i=a; i<=b; i++) {
        int x = i, m = 0;  // x保存原始数值，m用于存储反转后的数
        
        // 内部while循环：将数字x反转，结果存储在m中
        while(x) {
            m = m*10 + x%10;  // 取x的末位数字，加到m的末尾
            x /= 10;          // 去掉x的末位数字
        }
        
        // 如果反转后的数等于原数，则为回文数
        if(m == i) cnt++;
    }
    cout << cnt;  // 输出回文数总数
    return 0;
}

思考：

• 外循环(i)遍历从a到b的每个数
• 内部使用while循环将数字反转，得到m
• 判断反转后的数m是否等于原数i
• 这个实验展示了在一个循环内使用另一种循环（while循环）的灵活性

20.3.3 回文质数

题目描述：回文质数是既是质数又是回文数的数，如151、131等。写一个程序找出范围(5≤a<b≤100,000)间的所有回文质数。

样例输入：

100 200

样例输出：

101
131
151
181
191

代码实现：

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;  // 读入范围边界
    
    // 外循环：遍历a到b的每个数
    for(int i=a; i<=b; i++) {
        bool f = true;  // 布尔变量f用来标记当前数是否为质数，初始假设为质数
        
        // 第一步：判断是否为质数
        if(i < 2) f = false;  // 小于2的数不是质数
        
        // 内循环：检查i是否能被2到sqrt(i)的数整除
        for(int j=2; j*j<=i; j++) {
            if(i % j == 0) {  // 如果i能被j整除
                f = false;    // 则i不是质数
                break;        // 找到一个因子就可以确定非质数，立即退出循环
            }
        }
        
        // 如果不是质数，跳过后续判断，继续下一个数
        if(f == false) continue;
        
        // 第二步：判断是否为回文数
        int x = i, m = 0;  // x保存原始数值，m用于存储反转后的数
        
        // 内部while循环：将数字x反转，结果存储在m中
        while(x) {
            m = m*10 + x%10;  // 取x的末位数字，加到m的末尾
            x /= 10;          // 去掉x的末位数字
        }
        
        // 如果是回文数（且前面已确认是质数），则输出
        if(m == i) cout << i << endl;
    }
    return 0;
}

思考：

• 这个实验结合了前两个实验的技巧
• 先判断数字是否为质数，如果不是则使用continue跳过后续步骤
• 再判断数字是否为回文数
• 这是一个很好的例子，展示了如何组合多种条件来解决复杂问题