UVA-686 - Goldbach’s Conjecture (II)

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 相同題目：ZOJ-d307

題意概要

對任意一個大於或等於 $4$ 的偶數 $n$，存在最少一對質數 $p_1$ 與 $p_2$ 使得 $n = p_1 + p_2$。題目給定一連串的偶數，而對應於每一個偶數，請找出共有幾對是符合上述要求的質數對。注意，$(p_1, p_2)$ 與 $(p_2, p_1)$ 視為相同的質數對。

• 分析：本題為簡單的質數問題。直接從 $2$ (因為所有數字必能與 $1$ 整除且 $1$ 不是質數) 開始至 $n / 2$ 找出所有的質數 $p$，並檢查 $n - p$ 是否為質數即可。另一種解法為：先建立好質數表，利用查表的方式判斷題目給定的數字可否為兩個質數的組合，此種方式速度會大幅提升。

Input

An integer is given in each input line. You may assume that each integer is even, and is greater than or equal to $4$ and less than $2^{15}$. The end of the input is indicated by a number 0.

Output

Each output line should contain an integer number. No other characters should appear in the output.

Sample Input

6
10
12
0

Sample Output

1
2
1