Problem Solving►UVa

UVa 10168 - Summation of Four Primes

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

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

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

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

Code

UVa 10168
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//Goldbach's Conjecture
#include<cstdio>
#include<cmath>
#define N 10000000

int main()
{
    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 %d\n", i, n - i);
    }

    return 0;
}