ITeye博客

一个计算质数的Java程序

mmdev · 2004-09-21 12:43 · Markdown

这个Java程序用来计算质数,基本原理就是判断整除,用一个ArrayList记录已知的质数,一开始放入3,5,7,11,13,17,19,23,29,然后从31开始对奇数进行for(int n=31; ;n+=2)循环,对每个待判断的n,用已知的质数依次判断是否能整除,如果得到一个新的质数,就把它放到ArrayList中。

特殊之处在于,我把它实现了序列化,每次启动时可以恢复到上次的状态,以下是源代码:

import java.io.*;
import java.util.*;

public class PrimeNumber implements Serializable
{
 private ArrayList list;
 private int nStart;

 public PrimeNumber()
 {
 list=new ArrayList(9);
 list.add(new Integer(3));
 list.add(new Integer(5));
 list.add(new Integer(7));
 list.add(new Integer(11));
 list.add(new Integer(13));
 list.add(new Integer(17));
 list.add(new Integer(19));
 list.add(new Integer(23));
 list.add(new Integer(29));
 nStart=31;
 }






 public void calculate(int number)
 {
 System.out.print("Start calculating prime numbers... ");
 if (number<=0)
 return;
 list.ensureCapacity(number);
 int nGot=0;
 boolean bPrime;
 int n;
 for(int nTest=nStart; ; nTest+=2)
 {
 bPrime=true;
 for(int i=0; i<list.size(); i++)
 {
 n=((Integer)(list.get(i))).intValue();
 if (nTest % n == 0)
 // not a prime number:
 {
 bPrime=false;
 break;
 }
 }
 if (bPrime) // found a prime number
 {
 list.add(new Integer(nTest));
 nGot++;
 System.out.print("\nFound "+nTest+", "+(number-nGot)+" left.");
 if (nGot==number) // ok, finish calculation.
 {
 nStart=nTest+2;
 System.out.println("\ndone.\n");
 return;
 }
 }
 }
 }

 public static boolean store(PrimeNumber obj)
 {
        ObjectOutputStream objOut = null;
 try
 {
 objOut=new ObjectOutputStream(new FileOutputStream("prime.obj"));
 objOut.writeObject(obj);
 return true;
 }
 catch(Exception e) {}
        finally {
            if(objOut!=null) {
                try { objOut.close(); } catch(Exception e) {}
            }
        }
 return false;
 }



 public static PrimeNumber load()
 {
 try
 {
 ObjectInput objIn=new ObjectInputStream(new FileInputStream("prime.obj"));
 PrimeNumber pn=(PrimeNumber)objIn.readObject();
 objIn.close();
 return pn;
 }
 catch(Exception e)
 {
 }
 return null;
 }


public void display()
 {
 System.out.print("\nThere are " + (list.size()+1) + " prime numbers.\n2\t");
 for(int i=0; i<list.size(); i++)
 {
 System.out.print(list.get(i).toString());
 System.out.print("\t");
 }
 System.out.println("\n");
 }
 
 public void displayLast()
 {
 int nStart=list.size()-20;
 System.out.println("\nThe last 20 prime numbers:");
 if(nStart<0)
 System.out.print("2\t");
 for(int i=nStart; i<list.size(); i++)
 {
 if (i>=0)
 System.out.print(list.get(i).toString()+"\t");
 }
 System.out.println("\n");
 }

 public void storeAsFile()
 {
 DataOutputStream dos = null;
 try {
 dos = new DataOutputStream(new BufferedOutputStream(
                  new FileOutputStream("prime.data")));
 dos.writeInt(2);
 for(int i=0; i<list.size(); i++) {
 dos.writeInt(((Integer)list.get(i)).intValue());
 }
 System.out.println("Prime numbers has been saved.\n");
 }
 catch(Exception e) {
 System.out.println("There is an error occured. Saving failed.\n");
 }
 finally {
 if(dos!=null) {
 try { dos.close(); } catch(Exception e) {}
 }
 }
 }
 
 public static void main(String[] args)
 {
 // first try to read from disk:
 System.out.print("Reading from file... ");
 PrimeNumber pn=PrimeNumber.load();
 if (pn==null)
 {
 System.out.println("failed.\nCreate a new calculator... done.");
 pn=new PrimeNumber();
 }
 else
 System.out.println("done.");
 int sel;
 do
 {
 System.out.println("==============================================================");
 sel=pn.getCommand();
 switch(sel)
 {
 case 1:
 pn.calculate(10);
 break;
 case 2:
 pn.calculate(100);
 break;
 case 3:
 pn.calculate(1000);
 break;
 case 4:
 pn.calculate(10000);
 break;
 case 5:
 pn.display();
 break;
 case 6:
 pn.displayLast();
 break;
 case 7:
 pn.storeAsFile();
 break;
 case 8:
 break;
 default:
 System.out.println("Invalid command.");
 }
 }while(sel!=8);
 System.out.print("\nWriting to file... ");
 System.out.println(PrimeNumber.store(pn)==true?"done.":"failed.");
 }
 
public int getCommand()
 {
 System.out.println(" Total "+(list.size()+1)+" prime numbers calculated. Select:");
 System.out.println(" 1. Calculate next 10 prime numbers.");
 System.out.println(" 2. Calculate next 100 prime numbers.");
 System.out.println(" 3. Calculate next 1000 prime numbers.");
 System.out.println(" 4. Calculate next 10000 prime numbers.");
 System.out.println(" 5. Display all prime numbers.");
 System.out.println(" 6. Display the last 20 numbers.");
 System.out.println(" 7. Save all prime numbers as a file.");
 System.out.println(" 8. Save all prime numbers and quit.");
 System.out.print  (" Your selection: ");
 int sel=0;
 try
 {
 InputStreamReader isr=new InputStreamReader(System.in);
 sel=isr.read()-48;
 }
 catch(IOException e){}
 return sel;
 }
}

还可以把所有质数导出到文件,每4byte是一个质数,从小到大排列。我用这个程序计算了100,000个质数,算到的最大的质数是1299709。

评论(0)

暂无评论。

评论功能维护中,当前仅展示历史评论。