洛谷-P1304 哥德巴赫猜想

题目描述

输入一个偶数 N，验证 4~N所有偶数是否符合哥德巴赫猜想：任何大于偶数可以写成两个质数之和。如果一个数不止一个分法，则输出第一个加数最小于其他分法的方案。例如，，则是错误的答案。

输入格式

第一行输入正偶数 N

输出格式

输出 (N - 2) / 2 行。对于第 i 行：

首先输出正偶数 2i+2，然后输出等号，再输出加和 2i+2 而第一个加数最小的两个质数，用加号分开。

输入输出样例

输入

10

输出

4=2+26=3+38=3+510=3+7

思路解析

本体的困难在于，在控制代码的整体结构时，我们应该将大问题分解为小问题。例如，我们可以将这个问题分为：①遍历4~N之间的所有偶数，②遍历2~N/2之间的所有数字(目的是满足两数之和等于N的条件)③判断n是否为质数。代码分别如下：

for (int i = 4; i <= n; i += 2) {    fun(i);    }

public static void fun(int n) {    int t = 0;    for (int i = 2; i <= n / 2; i++) {      //遍历        if (fun1(i) && fun1(n - i)) {            System.out.println(n + "=" + i + "+" + (n - i));            t = 1;        }        if (t == 1)            return;    }}

public static boolean fun1(int n) {    for (int i = 2; i <= Math.sqrt(n); i++) {        if (n % i == 0) {            return false;        }    }    return true;}

整体代码

package com.luogu;import java.util.Scanner;public class P1304 {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        for (int i = 4; i <= n; i += 2) {            fun(i);        }    }    public static void fun(int n) {        int t = 0;        for (int i = 2; i <= n / 2; i++) {      //遍历            if (fun1(i) && fun1(n - i)) {                System.out.println(n + "=" + i + "+" + (n - i));                t = 1;            }            if (t == 1)                return;        }    }    public static boolean fun1(int n) {        for (int i = 2; i <= Math.sqrt(n); i++) {            if (n % i == 0) {                return false;            }        }        return true;    }}