黑马程序员技术交流社区

标题: 歌德巴赫猜想,任何一个大于六的偶数可以拆分成两个质数... [打印本页]
作者: 王小丑    时间: 2013-1-28 19:02
标题: 歌德巴赫猜想,任何一个大于六的偶数可以拆分成两个质数...
本帖最后由 张向辉 于 2013-1-30 11:35 编辑

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

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



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

//打印出所有的可能

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);

}

}

}

作者: 陈丽莉    时间: 2013-1-28 20:50
       我说个大致思路
       记得之前参加算法的比赛有过类似的题，因为要验证的数据很多，所以先创建一个数组，存起从3开始查找到的能存下的所有质数。然后验证一个大于六的偶数num时，双重循环，外循环a范围是从3到小于num的质数（从存好的数组里查找），内循环寻找num-a是否在数组中，当然限制是从外循环角标向后查找，直至找到或数组中的数已大于num-a。
        因为要验证的数据比较庞大，这种先存储再查找的方法可以极大地降低时间复杂度。
作者: 黄鸿达    时间: 2013-1-29 07:02
本帖最后由 jy00228875 于 2013-1-29 07:20 编辑
  1. import java.util.*;
  2. public class 歌德巴赫猜想 {

  4. public static void main(String[] args) {
  5. while(true){
  6. show();
  7. }

  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. //遍历可能的质数

  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. }

  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. }



  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. }


  96. }
  97. }
复制代码
写了N个小时终于写完了，但是发现自己写了很多，不过功能总算实现了，打印所有组合。调式了N多次~~而且写完这个，好好研究下数组在内存的关系。{:soso_e130:}
作者: 肖亚光    时间: 2013-1-29 18:03
  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. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2