【NOI-题解】1137 - 纯粹素数1258 - 求一个三位数1140 - 亲密数对1149 - 回文数个数

一、前言

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》

本章节主要对自定义函数问题进行讲解，包括《1137 - 纯粹素数》《1258 - 求一个三位数》《1140 - 亲密数对》《1149 - 回文数个数》题目。

二、问题

问题：1137 - 纯粹素数

类型：自定义函数

---

题目描述：

纯粹素数是这样定义的：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。这样下去一直到最后剩下的个位数也还是素数。

求出所有小于 3000 的四位的纯粹素数。

输入：

无

输出：

按从小到大的顺序输出若干个纯粹素数，每行一个。

---

1.分析问题

1. 已知：所有小于3000的四位数。
2. 未知：求出所有小于 3000 的四位的纯粹素数。
3. 关系: 纯粹素数：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。这样下去一直到最后剩下的个位数也还是素数。

2.定义变量

	//二、定义变量（已知、未知、关系） int t;bool isFind;

3.输入数据

无。

4.数据计算

• isPrime 函数：这个函数用于检测一个整数 p 是否为素数。
  • 首先处理特殊情况：小于等于3的数，其中1不是素数，2和3是素数。
  • 然后排除所有能被2或3整除的数。
  • 最后，从5开始，每次增加6，检查形如 6k ± 1 的数是否能整除 p。这是因为除了2和3外，所有素数都可以表示为 6k ± 1 的形式。

bool isPrime(int p){if(p<=3) return p>1;if(p%2==0 || p%3==0) return false;for(int i=5;i*i<=p;i+=6){if(p%i==0||p%(i+2)==0) return false;}return true;
}

• reHigh 函数：这个函数用于去掉一个数的最高位。
  • 如果数小于等于9，则返回0（因为已经没有更高位可以去掉了）。
  • 使用模运算和除法来构建新的数，去掉最高位。

int reHigh(int r){	if(r<=9) return 0;int res=0,mul=1;while(r>9){res+=r%10*mul;r/=10;mul*=10;}return res;
}

• 遍历从1001到2999之间的所有奇数（因为除了2以外的所有偶数都不是素数）。
  • 对于每个数，检查它及其去掉最高位后的数是否均为素数。
  • 如果是纯粹素数，则输出该数。

//四、根据关系计算for(int i=1001;i<3000;i+=2){t=i;isFind=true;while(t){if(!isPrime(t)){isFind=false;break;	}t=reHigh(t);}//五、输出未知 if(isFind) cout<<i<<endl;} 

完整代码如下：

#include<bits/stdc++.h>
using namespace std;// 检测一个整数是否为素数
bool isPrime(int p){// 处理特殊情况：小于等于3的数if(p <= 3) return p > 1; // 1不是素数，2和3是素数// 排除能被2或3整除的数if(p % 2 == 0 || p % 3 == 0) return false;// 从5开始检查形如 6k ± 1 的数for(int i = 5; i * i <= p; i += 6){if(p % i == 0 || p % (i + 2) == 0) return false;}return true; // 如果没有找到因子，则p是素数
}// 去掉一个数的最高位
int reHigh(int r){	if(r <= 9) return 0; // 如果只有一个数字，则返回0int res = 0, mul = 1;while(r > 9){res += r % 10 * mul; // 添加最低位数字到结果r /= 10; // 移除最低位mul *= 10; // 更新乘数}return res; // 返回去掉最高位后的数
}int main(){// 主循环：遍历所有小于3000的四位数for(int i = 1001; i < 3000; i += 2){ // 从1001开始，每次增加2（跳过偶数）int t = i;bool isFind = true;// 检查当前数及其去掉最高位后的数是否均为素数while(t){if(!isPrime(t)){isFind = false;break; // 如果发现任何一个数不是素数，则退出循环}t = reHigh(t); // 去掉最高位}// 如果所有去掉最高位后的数均为素数，则输出原始数if(isFind) cout << i << endl;} return 0; // 程序结束
}

---

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》

问题：1258 - 求一个三位数

类型：自定义函数、简单循环

---

题目描述：

求这样一个三位数，该三位数等于其每位数字的阶乘之和， 即
abc=a!+b!+c!。n! 表示 n 的阶乘, n!=1×2×3×⋯×n，如：5!=1×2×3×4×5)

输入：

无

输出：

输出这个数。

---

1.分析问题

1. 已知：所有的三位数。
2. 未知：找出符合条件的数。
3. 关系：该三位数等于其每位数字的阶乘之和。

2.定义变量

	//二、定义变量（已知、未知、关系） int g,s,b;

3.输入数据

无。

4.数据计算

• jc 函数：计算一个整数的阶乘。
  • 输入参数 t 表示要计算阶乘的数。
  • 使用一个循环来计算阶乘。
  • 返回阶乘的结果。

int jc(int t){int res=1;while(t>1){res*=t;--t;}return res;
}

• 遍历从100到999的所有三位数。
  • 对于每个数 i，获取个位、十位和百位上的数字。
  • 计算每一位数字的阶乘。
  • 检查该数是否等于各位数字的阶乘之和。
  • 如果条件满足，则输出该数，并结束循环。

//四、根据关系计算for(int i=100;i<1000;++i){g=i%10;s=i/10%10;b=i/100;g=jc(g);s=jc(s);b=jc(b);//五、输出未知if(i==g+s+b){cout<<i;break;}} 

完整代码如下：

#include<bits/stdc++.h>
using namespace std;// 计算阶乘的函数
int jc(int t){int res = 1;while (t > 1) {res *= t;--t;}return res;
}int main(){// 一、分析问题// 已知：所有的三位数。// 未知：找出符合条件的数。// 关系: 该三位数等于其每位数字的阶乘之和。// 二、定义变量（已知、未知、关系）int g, s, b; // 个位、十位、百位上的数字// 三、输入已知// 四、根据关系计算for (int i = 100; i < 1000; ++i) { // 遍历所有的三位数g = i % 10; // 获取个位数字s = i / 10 % 10; // 获取十位数字b = i / 100; // 获取百位数字// 计算每一位数字的阶乘g = jc(g);s = jc(s);b = jc(b);// 五、输出未知if (i == g + s + b) { // 如果该数等于各位数字的阶乘之和cout << i; // 输出该数break; // 找到一个符合条件的数后，结束循环}}return 0; // 程序结束
}

---

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》

问题：1140 - 亲密数对

类型：自定义函数

---

题目描述：

键盘输入 N ，N 在 2 至 2000 之间，求 2 至 N 中的亲密数对，就是 A 的因子和等于 B ，B 的因子和等于 A ，且 A≠B 。
如 48 和 75 是亲密数对。48 的因子和为 2+3+4+6+8+12+16+24=75 ，而 75 的因子和为 3+5+15+25=48 。

输入：

只有一行，为一个整数 N （ 2≤N≤2000 ）

输出：

输出若干行，每行两个整数（用一个空格隔开）。

样例1：

输入：

200

输出：

48 75
75 48
140 195
195 140

样例2：

输入：

150

输出：

48 75
75 48

---

1.分析问题

1. 已知：一个整数N ,N 在 2 至 2000 之间;
2. 未知：求 2 至 N 中的亲密数对;
3. 关系：A 的因子和等于 B ，B 的因子和等于 A ，且 A≠B 。

2.定义变量

• n表示输入的最大值，t用于临时存储因子和。

	//二、定义变量（已知、未知、关系）int n,t; 

3.输入数据

• 输入n的值

	//三、输入已知cin>>n;

4.数据计算

• 定义了一个名为sumYz的函数，用来计算小于或等于s的所有真因子之和。
  • 函数内部使用一个循环来找到所有的因子，并累加它们的值。
  • 如果一个因子的平方等于s，说明这个因子被重复计算了两次，需要减去一次。
  • 返回所有因子的累加和。

int sumYz(int s){int res=0;for(int i=2;i*i<=s;++i){if(s%i==0) res+=i+s/i;if(i==s/i) res-=i;}return res;
}

• 使用一个循环遍历从2到n的所有整数。
  • 对于每一个整数i，调用sumYz函数计算它的因子和t。
  • 检查t是否在2到n的范围内，同时检查i是否是t的因子和，并且i不等于t。
  • 如果满足条件，则输出这对亲和数。

	//四、根据关系计算for(int i=2;i<=n;++i){t=sumYz(i);//五、输出未知 if(t<=n&&sumYz(t)==i&&i!=t) cout<<i<<" "<<t<<endl;}

完整代码如下：

#include<bits/stdc++.h> // 包含所有标准C++库
using namespace std;// 计算一个整数s的所有真因子之和
int sumYz(int s){int res = 0; // 初始化结果为0// 遍历所有可能的因子for(int i = 2; i * i <= s; ++i){if(s % i == 0){ // 如果i是s的一个因子res += i + s / i; // 将i及其对应的配对因子加入结果}if(i == s / i) // 如果i的配对因子与i相同（即s是完全平方数）res -= i; // 避免重复计数}return res; // 返回所有真因子之和
}int main(){// 一、分析问题// 已知：一个整数N, N在2至2000之间;// 未知：求2至N中的亲和数对;// 关系: A的因子和等于B，B的因子和等于A，且A≠B。// 二、定义变量（已知、未知、关系）int n, t; // n表示输入的最大值，t用于临时存储因子和// 三、输入已知cin >> n; // 输入n的值// 四、根据关系计算for(int i = 2; i <= n; ++i){t = sumYz(i); // 计算i的所有真因子之和// 五、输出未知// 检查t是否也在2至n的范围内，并且i和t互为亲和数if(t <= n && sumYz(t) == i && i != t)cout << i << " " << t << endl; // 输出这对亲和数}return 0; // 主函数结束
}

---

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》

问题：1149 - 回文数个数

类型：自定义函数、2015江苏省青少年信息学奥林匹克竞赛复赛

---

题目描述：

一个正整数，正读和反读都相同的数为回文数。

例如22 ， 131 ， 2442 ， 37073 ， 6 ，… 所有 1 位数都是回文数。

给出一个正整数 n （ 1≤n≤10000 ），求出 1,2,…,n 之中（包括 1 和 n ）的回文数的个数。

输入：

任意给定一个正整数 n （ 0<n≤10000 ）

输出：

一个正整数，表示[ 1,n ]之间的回文数的个数。

样例：

输入：

325

输出：

41

---

1.分析问题

1. 已知：一个正整数 n （ 0<n≤10000 ）;
2. 未知：求出 1,2,…,n 之中（包括 1 和 n ）的回文数的个数;
3. 关系：一个正整数，正读和反读都相同的数为回文数。

2.定义变量

• 定义变量n用于存储用户输入的最大值，c用于计数回文数的数量。

	//二、定义变量（已知、未知、关系） int n,c=0;

3.输入数据

• 使用cin从用户获取输入值n。

	//三、输入已知cin>>n;

4.数据计算

• 判断一个整数h是否为回文数。
  • 初始化t为h的副本，r为0。
  • 使用一个循环反转h的数字。
  • 如果反转后的数字等于原数字，则返回true。

bool isHw(int h){int t=h,r=0;while(t){r=r*10+t%10;t/=10;}if(h==r) return true;return false;
}

• 使用一个循环从1到n遍历所有整数。
• 对于每个整数i，如果isHw(i)返回true，则增加计数器c。

	//四、根据关系计算for(int i=1;i<=n;++i){if(isHw(i)) ++c;}

5.输出结果

• 最后，使用cout输出回文数的总数c。

	//五、输出未知 cout<<c;

完整代码如下：

#include<bits/stdc++.h> // 包含所有标准C++库
using namespace std;// 判断一个整数是否为回文数
bool isHw(int h){int t = h, r = 0; // 初始化反转后的数字r为0，t用于存储原始数字的副本// 反转数字while(t){r = r * 10 + t % 10; // 反转操作t /= 10; // 去除最低位}// 检查原数字和反转后的数字是否相等if(h == r) return true; // 如果相等，则是回文数return false; // 否则不是回文数
}int main(){// 一、分析问题// 已知：一个正整数 n （ 0<n≤10000 ）;// 未知：求出 1,2,…,n 之中（包括 1 和 n ）的回文数的个数;// 关系: 一个正整数，正读和反读都相同的数为回文数。// 二、定义变量（已知、未知、关系）int n, c = 0; // n表示输入的最大值，c用于计数回文数的数量// 三、输入已知cin >> n; // 输入n的值// 四、根据关系计算for(int i = 1; i <= n; ++i){if(isHw(i)) ++c; // 如果i是回文数，则增加计数器}// 五、输出未知cout << c; // 输出回文数的总个数return 0; // 主函数结束
}

三、感谢

如若本文对您的学习或工作有所启发和帮助，恳请您给予宝贵的支持——轻轻一点，为文章点赞；若觉得内容值得分享给更多朋友，欢迎转发扩散；若认为此篇内容具有长期参考价值，敬请收藏以便随时查阅。

每一次您的点赞、分享与收藏，都是对我持续创作和分享的热情鼓励，也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇，共同攀登知识的高峰！

欢迎关注本专栏《C++从零基础到信奥赛入门级（CSP-J）》