首页 > itarticle > uva 10168 – summation of four primes

uva 10168 – summation of four primes

admin 11月 12, 2020 0

Contents

Problem

題目網址
 中文網址

Solution

利用 Goldbach’s Conjecture ，可將大於等於 4 的偶數拆成兩個質數。

n 如果為偶數，就直接拆成 4 + x (偶數加偶數)，$4 = 2 + 2$ ，x 大於等於 4 ，可拆成兩個質數。

n 如果為奇數，拆成 5 + x (奇數加偶數)，$5 = 2 + 3$ ，x 大於等於 4 ，可拆成兩個質數。

Code



#include<cmath>
#define N 10000000

int ()
{
    static bool sieve[N] = { 1, 1 };
    int SQRT = sqrt(N);
    for (int i = 2; i <= SQRT; i++)
        if (!sieve[i])
            for (int j = i << 1; j < N; j += i)
                sieve[j] = true;

    int n, i;
    while (scanf("%d", &n) != EOF)
    {
        if (n < 8)
        {
            puts("Impossible.");
            continue;
        }

        if (n & 1)
        {
            n -= 5;
            printf("2 3 ");
        }
        else
        {
            n -= 4;
            printf("2 2 ");
        }

        for (i = 2; i < n; i++)
            if (!sieve[i] && !sieve[n - i])
                break;

        printf("%d %dn", i, n - i);
    }

    return 0;
}