Problem Solving►UVa

UVa 543 - Goldbach's Conjecture

Contents

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

Problem

題目網址
中文網址

Solution

注意要找 b - a 最大的那組即可。

Code

UVa 543
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
#include<cstdio>
#include<cmath>
#define N 1000000

int main()
{
    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;
    while (scanf("%d", &n) && n)
    {
        int half = n >> 1;
        for (int i = 2;i<=half;i++)
            if (!sieve[i] && !sieve[n - i])
            {
            printf("%d = %d + %d\n", n, i, n - i);
            break;
            }
    }

    return 0;
}