java洛谷P1304 哥德巴赫猜想

哥德巴赫猜想是指任何一个大于2的偶数都可以表示成两个质数之和。这个猜想虽然在小范围内经过验证，但是一直没有被证明。洛谷P1304就是要求我们验证这个猜想在一定范围内是否成立。

具体来说，题目要求我们在给定的范围内（2<=n<=10000），找出所有满足条件的偶数，并输出它们的分解形式。如果有多组解，输出任意一组即可。

解题思路：我们可以先预处理出2~10000之间的所有质数，然后枚举每个偶数，判断它是否可以表示成两个质数之和。具体实现可以使用双指针法，从两端开始向中间逼近，如果和大于目标值，则右指针左移；如果和小于目标值，则左指针右移；如果和等于目标值，则找到了一组解。

参考代码如下：

import java.util.*;

public class Main {
    static final int N = 10010;
    static boolean[] isPrime = new boolean[N];
    static int[] primes = new int[N];
    static int cnt;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        getPrimes();
        while (n != 0) {
            for (int i = 0; primes[i] <= n / 2; i++) {
                int j = n - primes[i];
                if (isPrime[j]) {
                    System.out.printf("%d=%d+%d\n", n, primes[i], j);
                    break;
                }
            }
            n = scan.nextInt();
        }
    }

    static void getPrimes() {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i < N; i++) {
            if (isPrime[i]) {
                primes[cnt++] = i;
                for (int j = i * i; j < N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}