goldbach.java

Java 2 程序设计实用教程（第2版）[程序源代码]实验

//【习2.13】  编程验证哥德巴赫猜想。

public class Goldbach
{
    static final int MAX=30;                     //数据范围 
    static int[] prime=null;                     //存放素数的一维数组
    static int number;                           //素数个数，即数组的实际元素个数
    
    public Goldbach(int n)                       //输出n的哥德巴赫算式
    {
        if (prime==null)
            init();                              //初始化数组，筛选法求素数，只执行一次

        if (n%2==0)                              //偶数  
        {
            int i=0;
            while (i<number && prime[i]<=n/2)
            {
                if (isPrime(n-prime[i]))
                    System.out.print(n+"="+prime[i]+"+"+(n-prime[i])+"    ");
                i++;
            }
        }
        else                                     //奇数 
        {
            int i=0;
            while (i<number && prime[i]<=n/3)
            {
                int j=i;                         //如果j=0，则会出现重复的算式
                while (j<number && prime[j]<=n/3)
                {
                    if (isPrime(n-prime[i]-prime[j]))
                        System.out.print(n+"="+prime[i]+"+"+prime[j]+"+"+(n-prime[i]-prime[j])+"    ");
                    j++;
                }  
                i++;
            }
        }
        System.out.println();
    }

    public static void init()                    //初始化数组，筛选法求素数
    {
        prime = new int[MAX/2];
        prime[0]=2;                              //已知的最小素数
        number=1;                                //素数个数
        int i=1;                                 //下一个素数应存放的数组下标位置
        int k=3;                                 //从最小奇数开始测试，所有偶数不需测试
        do
        {
            int j=0;
            while ((j<number) && (k % prime[j]!=0))     //用已知素数prime[j]测试k
                j++;                    
            if (j==number)                       //k是素数
            {
                prime[i]=k;                      //将k添加到数组prime中
                i++;
                number++;
            }
            k+=2;                                //测试下一个奇数是否是素数
        }  while(k<MAX);
        output();
    }

    public static void output()                  //输出素数
    {
        System.out.println("All primes in 2~"+MAX+" are: ");
        for (int i=0;i<number;i++)
        {
            System.out.print("  "+prime[i]);
            if ((i+1)%10==0)
                System.out.println();            //每行写10个数
        }
        System.out.println("\nnumber="+number);
    }    
    
    public static boolean isPrime(int k)         //判断k是否为素数，即在prime中查找k值
    {  
        boolean  yes=false;
        int i=0;
        while (!yes && i<=number && prime[i]<=k)
            if (prime[i]==k)
               yes=true;
            else i++;
        return yes;
    }    

    public static void main(String args[]) 
    {
        for(int i=4;i<Goldbach.MAX;i+=2)
            new Goldbach(i);
            
        for(int i=7;i<Goldbach.MAX;i+=2)
            new Goldbach(i);
    }    
}

/*
程序运行结果如下：
All primes in 2~30 are: 
	2	3	5	7	11	13	17	19	23	29
number=10

偶数
4=2+2   
6=3+3   
8=3+5   
10=3+7      10=5+5  
12=5+7  
14=3+11     14=7+7  
16=3+13     16=5+11 
18=5+13     18=7+11 
20=3+17     20=7+13 
22=3+19     22=5+17     22=11+11    
24=5+19     24=7+17     24=11+13    
26=3+23     26=7+19     26=13+13    
28=5+23     28=11+17    

奇数
7=2+2+3 
9=2+2+5     9=3+3+3 
11=2+2+7    11=3+3+5    
13=3+3+7    
15=2+2+11   15=3+5+7    15=5+5+5    
17=2+2+13   17=3+3+11   17=5+5+7    
19=3+3+13   19=3+5+11   
21=2+2+17   21=3+5+13   21=3+7+11   21=5+5+11   21=7+7+7    
23=2+2+19   23=3+3+17   23=3+7+13   23=5+5+13   23=5+7+11   
25=3+3+19   25=3+5+17   25=5+7+13   25=7+7+11   
27=2+2+23   27=3+5+19   27=3+7+17   27=5+5+17   27=7+7+13   
29=3+3+23   29=3+7+19   29=5+5+19   29=5+7+17   

不能有重复表达式，例如
19=3+3+13   19=3+5+11   19=5+3+11
21=2+2+17   21=3+5+13   21=3+7+11   21=5+3+13   21=5+5+11   21=7+3+11   21=7+7+7

*/