题目要求
鸿鸿哥最近和一个小伙伴做了个小项目,赚了一个亿,两人一起高高兴兴开了庆功宴之后,鸿鸿哥就准备分一下钱了。鸿鸿哥想了想,生意不是做一天的,所以一个亿之中的大部分资金还是要继续投资,不能只是做一发就走,这个想法也得到了小伙伴的认可。而余下来的钱不知道具体数值,只知道是x万~y万之间(因为某种神秘力量余下的钱一定是偶数万)。而鸿鸿哥原本也是土豪,这点小钱也看不上眼,于是他想分多一点给小伙伴,他决定把钱分成两个素数(程序员喜欢各种特别的数字),自己拿小的那份。那么问题来了,鸿鸿哥和小伙伴个各拿多少万呢?鸿鸿哥想知道所有可能的分法。
输入格式:
输入两个整数x,y(6<=x,x<=y,n<=100),一组输入。
输出格式:
输出x和y之间所有偶数表示成的两个素数之和。
输入样例:
8 10
输出样例:
8=3+5
10=3+7
解题思路
使用判断素数的函数 is_prime,该函数接受一个整数 n 作为参数,返回值为 bool 值。函数内部采用了经典的素数判断方法,枚举从 2 到 sqrt(n) 的所有正整数,如果其中有一个可以整除 n,则说明 n 不是素数,返回 false。如果上述枚举过程结束后仍然没有找到能整除 n 的数,则说明 n 是素数,返回 true。
is_prime函数
is_prime 函数是用来判断一个数是否为素数的函数。其输入为一个整数 n,输出为一个 bool 类型的值,若 n 为素数则返回 true,否则返回 false。
下面是一个常见的实现方式:
bool is_prime(int n) { if (n <= 1) { // 1 不是素数,小于等于 1 的数都不是素数 return false; } for (int i = 2; i <= sqrt(n); i++) { // 枚举从 2 到 sqrt(n) 的所有数 if (n % i == 0) { // 如果 n 能被某个数整除,则说明 n 不是素数 return false; } } return true; // 否则 n 是素数 }
该实现方式首先判断输入的数是否小于等于 1,如果是,则该数不是素数,直接返回 false
之后,从 2 到 sqrt(n) 枚举每个整数,如果存在一个能够整除 n 的数 i,则 n 显然不是素数,因此返回 false
最后,若上述循环结束后没有找到能够整除 n 的数,则 n 是素数,返回 true。
使用素数分解的函数 decompose,该函数接受一个整数 c 作为参数,无返回值。函数内部通过枚举从 2 到 c/2 的所有正整数 i 和 c-i,判断它们是否都是素数。找到符合条件的 i 和 c-i 后输出分解式 c = i + (c-i),然后退出函数。
decompose函数
decompose 函数是用来对一个偶数进行素数分解的函数。其输入为一个整数 a,表示需要对 a 进行素数分解,无返回值。
下面是一个常见的实现方式:
void decompose(int c) { for (int i = 2; i <= c/2; i++) { // 只需枚举到 c/2 即可 if (is_prime(i) && is_prime(c-i)) { // 判断 i 和 c-i 是否均为素数 cout << c << "=" << i << "+" << c-i << endl; // 输出分解式 break; // 找到一个解即可退出循环 } } }
该实现方式首先从 2 到 a/2 枚举每个正整数 i,判断 i 是否为素数,如果不是素数则跳过当前循环。
之后,判断 a-i 是否为素数,如果不是素数则跳过当前循环。如果 i 和 a-i 均为素数,则输出分解式 a = i + (a-i),并且退出循环。
主函数 main其读取两个整数 x, y,表示要对区间 [x, y] 内的所有偶数进行素数分解。首先判断 x 是否为偶数,如果不是偶数则将其加 1。之后,从 x 开始,每次扫描下一个偶数并调用函数 decompose 进行素数分解,直到扫描到 y 为止。
代码
具体实现代码如下:
#include <iostream> #include <cmath> using namespace std; bool is_prime(int n) { // 判断素数函数 if (n <= 1) { return false; } for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } void decompose(int a) { // 素数分解函数 for (int i = 2; i <= a/2; i++) { // 只需枚举到 a/2 即可 if (is_prime(i) && is_prime(c-i)) { cout << a << "=" << i << "+" << a-i << endl; break; // 找到一个解即可退出循环 } } } int main() { int x, y; cin >> x >> y; if (x % 2 != 0) { // 如果 x 不是偶数,则将其加 1 x++; } for (int i = x; i <= y; i += 2) { // 对于偶数区间内的每一个数进行分解 decompose(i); } return 0; }
值得注意的是,主函数中有对decompose函数进行循环遍历,因此在 decompose 函数中,只要找到一个符合条件的解即可退出循环。
头文件
cmath 是 C++ 标准库中的一个头文件,其中定义了许多和数学相关的函数。在本题中,使用了 cmath 中的 sqrt 函数。
sqrt 函数用于计算平方根,其形式如下:
double sqrt(double x);
float sqrt(float x);
long double sqrt(long double x);
该函数接收一个浮点数 x 作为参数,返回值为其平方根。在 is_prime 函数中,使用了 sqrt(n) 表示 n nn 的平方根,以方便判断其是否是素数。
总结
本文使用is_prime函数及decompose函数实现对给定的一个区间内所有偶数进行素数分解,读者可躬身实践。
我是秋说,我们下次见。