洛谷新手村的一天--关于验证歌德巴赫猜想的题解

    xiaoxiao2022-07-07  203

    题目描述 现在请你编一个程序验证哥德巴赫猜想。

    先给出一个奇数n,要求输出3个质数,这3个质数之和等于输入的奇数。

    输入输出格式 输入格式: 仅有一行,包含一个正奇数n,其中9<n<20000

    输出格式: 仅有一行,输出3个质数,这3个质数之和等于输入的奇数。相邻两个质数之间用一个空格隔开,最后一个质数后面没有空格。如果表示方法不唯一,请输出第一个质数最小的方案,如果第一个质数最小的方案不唯一,请输出第一个质数最小的同时,第二个质数最小的方案。

    刚拿到手时,蒟蒻的内心是蒙的,对于质数分解是不大熟悉,所以就选择了看大佬的题解,其中有一道还是很容易理解的,在这里记一下思路。

    抓住的关键点为奇数。在此基础上进行了优化。

    奇数=奇数+奇数+奇数

    1.我们选择最小的奇质数3作为第一位开始循环。 2.用i开始循环,判断是否为奇数且为质数。 3因为题设要求第二位大于第一位,扫来旮旯 选择j=i开始简化一下; 同上一步判断奇数与质数 4最后偷个懒,直接n-i-j判断是否为奇数和质数即可;

    奇数=偶数+偶数+奇数

    这里其实挺容易,可我当时就是不知道怎么开始。 最小的偶质数为2;那么 结论还不简单 2 2 n-4; 我真傻,真的。

    鉴于这里判断质数用的多,可以直接写一个函数作为判断。

    最新回复(0)