试题 算法提高 哥德巴赫猜想
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
根据所给函数(判断一个整数是否是素数),然后依托该函数,将输入N内的偶数(6-N),输出为两个素数之和(要求为可行的第一种分解),并各自验证哥德巴赫猜想:任何一个大于等于6的偶数(验证6到0x7FFFFF之间的偶数即可)都可以表示成两个素数之和,注意,此处不要求验证哥德巴赫猜想。
输入格式
测试数据的输入一定会满足的格式。
7
输出格式
要求用户的输出满足的格式。
6=3+3
样例输入
一个满足题目要求的输入范例。
例:
30
样例输出
与上面的样例输入对应的输出。
例:
6=3+3
8=3+5
10=3+7
12=5+7
14=3+11
16=3+13
18=5+13
20=3+17
22=3+19
24=5+19
26=3+23
28=5+23
数据规模和约定
输入数据中每一个数的范围。
例:0<n,m<100, 0<=矩阵中的每个数<=1000。
import java.util.ArrayList;
import java.util.Scanner;
public class 哥德巴赫猜想2 {
public static ArrayList<Integer> list = new ArrayList<Integer>();
public static int n=0;
public static String [] num ;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
num = new String [n];
zhishu();
f(0,0);
for (int i = 6; i <n; i+=2) {
System.out.println(i+num[i]);
}
}
public static void f(int start,int end){
if(end>=list.size() || start>=list.size()) return;
int temp = list.get(start)+list.get(end);
if(temp>=n ) return;
if(num[temp]==null)
num[temp]="="+list.get(start)+"+"+list.get(end);
f(start,++end);
f(++start,end);
}
public static void zhishu(){
A: for (int i = 2; i <n; i++) {
int sqrt=(int) Math.sqrt(i);
for(int num:list){
if(i%num==0){
continue A;
}
else if(num>sqrt)
break;
}
list.add(i);
}
}
}