Question

如何用Java验证哥德巴赫猜想？

Answer 1

　　哥德巴赫猜想原描述是“任一大于5的整数都可写成三个质数之和”，欧拉给出等价版本，即“任一大于2的偶数都可写成两个质数之和”，今日常见的陈述为欧拉版本。
　　使用Java验证哥德巴赫猜想的代码如下（在代码中要求输入大于6的数字是因为4=2+2、6=3+3，算法直接从8开始验证）：

package algorithms;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class GoldbachConjecture {

public static void main(String[] args) {
int i, j, n = 0, f1, f2, m = 0;
System.out.println("验证哥德巴赫猜想。");
System.out.println("输入一个大于6的偶数：");
BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
try {
m = Integer.parseInt(rr.readLine());
} catch (IOException e) {
}
for (i = 3; i < m / 2; i += 2) {
f1 = f2 = 0;
for (j = 3; j <= i / 2; j += 2) {
if (i % j == 0) {
f1 = 1;
break;
}
}
if (f1 == 1)// 如果i不是质数,下一个i
continue;
// 直到找到一个质数i,这是肯定可以找到的
n = m - i;
for (j = 3; j <= n / 2; j += 2) {
if (n % j == 0) {
f2 = 1;
break;
}
}
if (f2 == 1)
continue;
else
break;
}
System.out.println("大于等于6的偶数" + m + "可以分解为:");
System.out.println(i + "与" + n + "两数之和");
}
}

Answer 2

对于任何一个大于2的偶数n，我们可以将其分解为对应两个数之和，如：n=1+(n-1),n=2+(n-2)……,n=(n/2-1)+(n/2+1),n=n/2+n/2,之后的组合如n=(n/2+1)+(n/2-1)已经和之前的组合重复了。

分解的一个数只要从1到n/2就可以了，之后我们需要判断组合的两个数是否为质数，如果是质数，那么该组合舍弃，进行下一对组合判断，如果没有直到结束也没有出现合适组合，那么验证就失败了。

那么如何判断是不是质数？在一般领域，对正整数n，如果用2到√n之间的所有整数去除，均无法整除，则n为质数。质数大于等于2 不能被它本身和1以外的数整除。