---
title: 'UVa 543 題解 — C++'
disqus: hackmd
---

# UVa 543 題解 — C++
:::info
:bulb: 此筆記為UVa 543的題目詳解，包含解題思路、C++範例程式碼。
（ZeroJudge 的編號是錯的喔！）
:::

## Goldbach's Conjecture (ZeroJudge c050.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=c050)
:::success
在1742年一個德國業餘數學家Christian Goldbach，他作了以下的猜測：
任何一個比4大的偶數一定能夠找到2個奇數的質數使其和相等。例如：

8=3+5（3和5都是奇數，且是質數）

20=3+17=7+13

42=5+37=11+31=13+29=19+23

你的任務就是寫一個程式來驗證他的猜測。

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in
which he made the following conjecture:
Every number greater than 2 can be written as the sum of three prime numbers.
Goldbach was considering 1 as a primer number, a convention that is no longer followed. Later on,
Euler re-expressed the conjecture as:
Every even number greater than or equal to 4 can be expressed as the sum of two 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 as expressed by Euler for all even numbers
less than a million.
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
利用質數篩法（Sieve of Eratosthenes）建立一個 0 ~ 1000000 的質數表。

然後再根據題目要求從小到大找第一組可以組合成目標整數 n 的質數，就是所求的 b - a 最大的那組。
:::

### 範例程式碼

#include <bits/stdc++.h>
using namespace std;

int table[1000001]={}; 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	long long int i, j, n, a, b;
	
	for (i=0;i<=1000000;i++)  //假設全部都是質數
		table[i] = 1;
	table[0] = 0;  //0 不是質數 
	table[1] = 0;  //1 不是質數 
	
	//建立質數表 
	for (i=2;i<=1000000;i++) {
		if (table[i] == 1) {  //如果 i 是質數 
			for (j=i*i;j<=1000000;j=j+i)  //把 i 的倍數都設為不是質數
				table[j] = 0; 
		}
	}
	
	while (cin >> n && n != 0) {
		for (i=2;i<n;i++) {
			if (table[i] == 1 && table[n-i] == 1) {  // i (a) 與 n - i (b) 為質數 
				a = i;
				b = n - i;
				
				break;  //最先找到的就是 a 跟 b 間距最大的 
			} 
		} 
		
		cout << n << " = " << a << " + " << b << endl;
	}

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (0.1s, 4.1MB)

###### tags: `CPE ?星`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::