洛谷P1579笔记

Lassie ·

更新时间:2024-09-21

· 571 次阅读

题目：任何一个大于9的奇数都可以表示成3个质数之和。
先给出一个奇数n，要求输出3个质数，这3个质数之和等于输入的奇数。

输入：仅有一行，包含一个正奇数n，其中9<n<20000

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

解析：

结果为奇数
偶数+偶数+奇数
全为奇数

质数最小的方案
其中偶数中只有2为质数，所以第一种：2 2 n-4
循环测试奇数，从3开始，这是第二种

#include
int IsPrime(int x) 
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0) 
            return 0;
    }   
    return 1;
}
int main() 
{
    int n;
    scanf("%d", &n);
    if (IsPrime(n - 4)) 
    {
        printf("2 2 %d", n - 4);
        return 0;
    }  //第一种情况
    for (int i = 3; i < n; i++)//第二种情况
    {
        if ((i % 2) != 0 && IsPrime(i))
        {
            for (int j = i; j < n; j++)
            {
                if ((j % 2) != 0 && IsPrime(j) && IsPrime(n - i - j))
                {
                    printf("%d %d %d", i, j, n - i - j);
                    return 0;  //立刻退出
                }
            }       
        }
    }
}

注：运用数学知识，分析题目

源自洛谷P1579的题解，重新整理

作者：鲁仲连

1024 个赞