[Offer收割]編程練習賽12 題目1 : 歌德巴赫猜想

?

時間限制:10000ms

單點時限:1000ms

內存限制:256MB

描述

哥德巴赫猜想認為“每一個大于2的偶數，都能表示成兩個質數之和”。

給定一個大于2的偶數N，你能找到兩個質數P和Q滿足P<=Q并且P+Q=N嗎？

輸入

一個偶數N(4 <= N <= 1000000)

輸出

輸出P和Q。如果有多組解，輸出P最小的一組。

樣例輸入

10

樣例輸出

3 7

?

思路

判斷和為N兩個數是否為素數

代碼

import java.util.Scanner;

public class Main {

    public static boolean isPrim(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 2; i + i <= n; i++) {
            if (isPrim(i) && isPrim(n - i)) {
                System.out.println(i + " " + (n - i));
                break;
            }
        }
    }
}

?