POJ 2262：Goldbach's Conjecture

Description

在1742年，Christian Goldbach，一个德国数学家发了一封邮件给欧拉，说明了他的猜想：

　　每个超过4的偶数都能写成两个素数相加。

比如：

　　8 = 3 + 5.
　　20 = 3 + 17 = 7 + 13. 
　　42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

现在这个猜想是否正确仍没有被证明（当然我已经证明了，但是因为证明过程太长了，所以就不写下来了）。不管怎样，你的任务是验证小于一百万的所有偶数是否满足这个猜想。

Input

输入包含了1个或多个测试用例。
每个测试用例是一个偶数n($6 \leq n<1000000$)。
输入以n=0终止。

Output

对于每个测试用例，输出一行类似“n = a + b”的形式，其中 a 和 b 都是素数。操作数和操作符都应该以空格分开。如果存在多对素数对加起来是n，则选择一对 b-a 最大的素数对。如果没有这样的素数对，则输出“Goldbach's conjecture is wrong.” 

Sample Input

8
20
42
0

Sample Output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

Source

思想：一次直接把[1,1000000]的素数全部算好，这样就不用重复运行筛选法了（事实上，重复运行筛选法会TLE）。

import java.util.Scanner;

public class Main {
    boolean[] arr;
    public void sieve(int n){
        arr = new boolean[n+1];
        for(int i=0;i<arr.length;i++)
            arr[i] = true;
        int bound = (int)Math.floor(Math.sqrt(n));    //根号n
        for(int i=2;i<=bound;i++){
            if(arr[i]){
                for(int j=2;j*i<=n;j++){
                    arr[i*j] = false;
                }
            }
        }
    }
    public void fun(int n){
        for(int i=2;i<=n/2;i++){
            if(arr[i] && arr[n-i]){
                System.out.println(n+" = "+i+" + "+(n-i));
                return;
            }
        }
        System.out.println("Goldbach's conjecture is wrong.");
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Main main = new Main();
        main.sieve(1000000);
        while(true){
            String line = in.nextLine().trim();
            int n = Integer.parseInt(line);
            if(n==0){
                return;
            }
            main.fun(n);
        }
    }
}