歌德巴赫猜想,任何一个大于六的偶数可以拆分成两个质数的和

要求：打印出所有的可能
参考答案如下，只是太麻烦了，求高手指教，给出一个简单的方法，最好能用递归实现！



//任何一个大于六的偶数可以拆分成两个质数的和

//打印出所有的可能

public class Gedebahe{

public static void main(String args[]){

int num = Integer.parseInt(args[0]);

if(num<=6){

System.out.println(“参数错误!”);

return;

}

if(num%2!=0){

System.out.println(“参数错误!”);

return;

}

Gedebahe g = new Gedebahe();

//1不是质数,2是偶数,因此从3开始循环

for(int i=3;i<=num/2;i++){

if(i%2==0){//如果为偶数,退出本次循环

continue;

}

//当i与num-i都为质数时,满足条件,打印

if(g.isPrime(i) && g.isPrime(num-i)){

System.out.println(i+” + “+(num-i)+” = “+num);

}

}

}

1. import java.util.*;
   
2. class Gedebahe
   
3. {
   
4.         public static void main(String[] args)
   
5.         {
   
6.                 Scanner sc = new Scanner(System.in);
   
7.                 System.out.println("请输入一个大于6的偶数");
   
8.                 int num = sc.nextInt();
   
9.                 while(num<=6||num%2!=0)
   
10.                 {
    
11.                         System.out.println("输入错误，请重新输入");
    
12.                         num = sc.nextInt();
    
13.                 }
    
14.                 for(int i = 3;i<num/2;)
    
15.                 {
    
16.                         if(!isZhishu(i)&&!isZhishu(num-i))
    
17.                         {
    
18.                                 System.out.println(num+"="+i+"+"+(num-i));
    
19.                         }
    
20.                         i = i+2;
    
21.                 }
    
22.         }
    
23.         public static boolean isZhishu(int num)
    
24.         {
    
25.                 boolean flag = false;
    
26.                 for(int i =2 ;i<num/2;i++)
    
27.                 {
    
28.                         if(num%i==0)
    
29.                         {flag=true;break;}
    
30.                         else
    
31.                                 flag=false;
    
32.                 }
    
33.                 return flag;
    
34.         }
    
35. }

复制代码

1. import java.util.*;
   
2. public class 歌德巴赫猜想 {
   
3. 
   
4. public static void main(String[] args) {
   
5. while(true){
   
6. show();
   
7. }
   
8. 
   
9. }
   
10. //输入目标数
    
11. public static int diguiInput(){
    
12. System.out.println("输入一个大于6的偶数");
    
13. int num=new Scanner(System.in).nextInt();
    
14. if(num>6){
    
15. if(num%2==0){
    
16. System.out.println("正确，你输入的数是"+num+"即将为你算");
    
17. return num;
    
18. }
    
19. else{
    
20. System.out.println("错误，你输入的数是"+num+"请重新输入");
    
21. num=diguiInput();
    
22. }
    
23. }
    
24. else{
    
25. System.out.println("错误，你输入的数是"+num+",请重新输入");
    
26. num=diguiInput();
    
27. }
    
28. return num;
    
29. }
    
30. //建立3到给定数之间的质数表
    
31. public static int[] zhishuArray(int num){
    
32. //遍历可能的质数
    
33. 
    
34. int[] arr=new int[num];
    
35. //保存质数
    
36. int[] brr=new int[num];
    
37. int count=0;
    
38. //算3到你给出的数之间的质数
    
39. for(int x=3;x<arr.length;x++){
    
40. for(int y=2;y<arr.length;y++){
    
41. if(x==y){
    
42. brr[count]=x;
    
43. count++;
    
44. }
    
45. if(x%y==0){
    
46. break;
    
47. }
    
48. }
    
49. }
    
50. return brr;
    
51. }
    
52. 
    
53. public static int[][] combot(int[] arr,int num){
    
54. int no1;
    
55. //int[] brr=new int[2];
    
56. int sum=num;
    
57. //临时创建一个二维数组存各种组合
    
58. int[][] crr=new int[num][2];
    
59. //记录二维数组角标
    
60. int count=0;
    
61. for(int x=0;x<arr.length/2;x++){
    
62. sum=num-arr[x];
    
63. no1=arr[x];
    
64. if(arr[x]>num/2){
    
65. break;
    
66. }
    
67. for(int y=0;y<arr.length;y++){
    
68. if(sum==arr[y]){
    
69. //brr[0]=no1;
    
70. //brr[1]=arr[y];
    
71. crr[count]=new int[]{no1,arr[y]};
    
72. count++;
    
73. }
    
74. }
    
75. }
    
76. //把临时的二维数组压缩成新的二维数组，不然输太大的数，占内存
    
77. int[][] drr=new int[count][2];
    
78. for(int x=0;x<drr.length;x++){
    
79. drr[x][0]=crr[x][0];
    
80. drr[x][1]=crr[x][1];
    
81. }
    
82. return drr;
    
83. }
    
84. 
    
85. 
    
86. 
    
87. public static void show(){
    
88. int num=diguiInput();
    
89. int[][] arr=combot(zhishuArray(num),num);
    
90. for(int x=0;x<arr.length;x++){
    
91. //if(arr[x][0]!=0|arr[x][1]!=0){
    
92. System.out.println(num+"拆分的质数是"+arr[x][0]+"和"+arr[x][1]);
    
93. }
    
94. 
    
95. 
    
96. }
    
97. }

复制代码

写了N个小时终于写完了，但是发现自己写了很多，不过功能总算实现了，打印所有组合。调式了N多次~~而且写完这个，好好研究下数组在内存的关系。{:soso_e130:}

       我说个大致思路
       记得之前参加算法的比赛有过类似的题，因为要验证的数据很多，所以先创建一个数组，存起从3开始查找到的能存下的所有质数。然后验证一个大于六的偶数num时，双重循环，外循环a范围是从3到小于num的质数（从存好的数组里查找），内循环寻找num-a是否在数组中，当然限制是从外循环角标向后查找，直至找到或数组中的数已大于num-a。
        因为要验证的数据比较庞大，这种先存储再查找的方法可以极大地降低时间复杂度。