现在的位置: 首页 > 综合 > 正文

POJ_2262

2018年04月13日 ⁄ 综合 ⁄ 共 2573字 ⁄ 字号小中大 ⁄ 评论关闭

一.题目

Goldbach's Conjecture

Time Limit: 1000MS

Memory Limit: 65536K

Description

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

Every even number greater than 4 can be
written as the sum of two odd prime numbers.

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)
Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.

Input

The input will contain one or more test cases.
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.

Output

For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the
sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."

Sample Input

Sample Output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

二.解题技巧

本题只是一个简单的将一个偶数分解为两个质数相加的形式，如果有多个这样的分解的话，就找出两个质数差值最大的情况，最简单的方法就是计算出1,000,000里面的所有质数，然后计算里面的所有的质数的和，最后根据给出的数值，找到和等于给定数值的质数组合，最后判断那个组合的差值最大，该方法很简单，但是，计算复杂度为

,
其中N为1,000,000以内的质数的个数，因此，该做法对于最大值为1,000,000来说，需要的时间太长了，因此，需要考虑其他简单的方法。

考虑本题中，是要求和为给定值的两个质数，也就是已知n,且n=a+b,现在要求的是a和b，使得a和b为质数，且b-a最大，设c=b-a,则可以得到下面的两个等式。

考虑到上面的两个式子，只要找到两个数的和以及他们的差值，就可以计算得到这两个数，因此，本题就可以转换为通过最大的差值计算得到的两个数是否为质数的问题。

伪代码如下：

输入：给定一个偶数n

输出：两个质数a和b,使得n=a+b,且b-a的差值最大

算法：Deal():

for （int tmp = n - 6; tmp > 0; tmp = tmp + 2)

a = (n - tmp) / 2;

if a不是质数，进入下一个循环

b = (n + tmp) / 2;

if b不是质数，进行下一个循环

输出a和b

三.实现代码

#include <iostream>
#include <math.h>

using namespace std;


bool IsPrime(int Value)
{

    if ((Value == 2) || (Value == 3))
    {
        return true;
    }

    if (0 == (Value % 2))
    {
        return false;
    }

    for (int Index = 3; Index <= sqrt((double(Value))); Index = Index + 2)
    {
        if (0 == (Value % Index))
        {
            return false;
        }
    }
    return true;
}


void Deal(int Value)
{
    int Min = 0;
    int Max = 0;

    for (int Tmp = Value - 6; Tmp >= 0; Tmp = Tmp - 2)
    {
        Min = (Value - Tmp) / 2;
        if (!IsPrime(Min))
        {
            continue;
        }

        Max = Value - Min;
        if (!IsPrime(Max))
        {
            continue;
        }

        cout << Value << " = " << Min << " + " << Max << endl;
        return;
    }

    cout << "Goldbach's conjecture is wrong." <<endl;

}


int main()
{

    int Value = 0;

    while(true)
    {
        cin >> Value;
        if (Value == 0)
        {
            break;
        }
        else
        {
            Deal(Value);
        }

    }

    return 0;
}

四.体会

本题并不是很难，只是一道简单的计算题，难点在于不能通过先直接计算1,000,000内的所有质数的两两的和,因为这个范围太大了，计算复杂度很高，因此，即使计算出来了这些质数两两之间的和，如何保存这些表达式也是一个需要考虑的问题，同时，在输入的值并不是很多的情况下，将所有的质数的两两之间的和计算出来，不仅浪费时间，也浪费空间，由于本题只是要求两个质数的差值最大，因此，其他和虽然是一样的，但是差值比较小的表达式就不用考虑了，通过一个数学转化，就可以将本题转化先通过求解最大差值，然后再进行质数判断的形式了。

有时一个小小的数学变换，就可以简化很多计算和存储空间，因此，写程序要多多思考，不能仅仅是会编码而已。