C++/PTA 鸿鸿哥分钱

简介: 鸿鸿哥最近和一个小伙伴做了个小项目,赚了一个亿,两人一起高高兴兴开了庆功宴之后,鸿鸿哥就准备分一下钱了。

题目要求

鸿鸿哥最近和一个小伙伴做了个小项目,赚了一个亿,两人一起高高兴兴开了庆功宴之后,鸿鸿哥就准备分一下钱了。鸿鸿哥想了想,生意不是做一天的,所以一个亿之中的大部分资金还是要继续投资,不能只是做一发就走,这个想法也得到了小伙伴的认可。而余下来的钱不知道具体数值,只知道是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函数实现对给定的一个区间内所有偶数进行素数分解,读者可躬身实践。

我是秋说,我们下次见。

目录
相关文章
|
7月前
|
C++
【PTA】L1-016 验证身份(C++)
【PTA】L1-016 验证身份(C++)
94 0
【PTA】L1-016 验证身份(C++)
|
6月前
|
存储 C++
【PTA】L1-039 古风排版(C++)
【PTA】L1-039 古风排版(C++)
56 1
|
7月前
|
Java C++
部落(pta)(并查集) Java以及C++
部落(pta)(并查集) Java以及C++
59 2
|
6月前
|
存储 人工智能 C++
【PTA】L1-064 估值一亿的AI核心代码(详C++)
【PTA】L1-064 估值一亿的AI核心代码(详C++)
51 1
|
6月前
|
存储 C++ 索引
【PTA】L1-059 敲笨钟(C++)
【PTA】L1-059 敲笨钟(C++)
49 1
|
6月前
|
存储 人工智能 C++
【PTA】L1-093 猜帽子游戏(C++)
【PTA】L1-093 猜帽子游戏(C++)
130 1
|
6月前
|
C++
【PTA】L1-046 整除光棍(C++)
【PTA】L1-046 整除光棍(C++)
71 1
|
6月前
|
存储 C++
【PTA】L1-043 阅览室(C++)
【PTA】L1-043 阅览室(C++)
35 1
|
6月前
|
存储 C++
【PTA】​L1-034 点赞(C++)
【PTA】​L1-034 点赞(C++)
32 0
|
7月前
|
前端开发 JavaScript 测试技术
【PTA】L1-32 Left-pad (C++)
【PTA】L1-32 Left-pad (C++)
45 0
【PTA】L1-32 Left-pad (C++)