判断素数

public class Prime {
	private static int MAX = 10000000;
	private int[] isPrime = new int[MAX];
	
	private void prime(){
		for(int i=0;i<MAX;i++){
			if(i==0 || i==1){
				isPrime[i] = 0;
			}else{
				isPrime[i] = 1;
			}
		}
		
		for(int i=2;i*i<MAX;i++){
			if(isPrime[i]==1){
				for(int j=i;j*i<MAX;j++){
					isPrime[j*i] = 0;
				}
			}
		}
	}
	
	public static void main(String...args){
		Prime p = new Prime();
		p.prime();
		long start = System.currentTimeMillis();
		/*for(int i=0;i<p.isPrime.length;i++){
			if(p.isPrime[i]==1){
				System.out.println(i+"是质数");
			}
		}*/
		long end = System.currentTimeMillis();
		System.out.println(end-start);
	}
}

评论

2 楼 lg_asus 2012-05-16  

上面代码有点小问题，最新代码：

public class Prime {
	private static int MAX = 1000000;
	private int[] isPrime = new int[MAX];
	
	private void prime(){
		for(int i=0;i<MAX;i++){
			if(i==0 || i==1){
				isPrime[i] = 0;
			}else{
				isPrime[i] = 1;
			}
		}
		
		for(int i=2;i*i<MAX;i++){
			if(isPrime[i]==1){
				for(int j=i;j*i<MAX;j++){
					isPrime[j*i] = 0;
				}
			}
		}
	}
	
	public static void main(String...args){
		long start = System.currentTimeMillis();
		Prime p = new Prime();
		p.prime();
		int j = 0;
		for(int i=0;i<p.isPrime.length;i++){
			if(p.isPrime[i]==1){
				j++;
				/*System.out.print(i+"\t");
				if(j%5==0){
					System.out.println();
				}*/
			}
		}
		System.out.println("\ntotal prime numbers: "+j);
		long end = System.currentTimeMillis();
		System.out.println("time consumed: "+(end-start));
	}
}

1 楼 lg_asus 2012-05-16  

测试10 million的以内的数据，算出所有素数时间在500多ms,不包括把数据打印出来的时间。

这个思想就是筛选法，首先把2的倍数去掉，再去3的倍数，依此类推。

其中耗时的工作在：
for(int i=2;i*i<MAX;i++){ 
            if(isPrime[i]==1){ 
                for(int j=i;j*i<MAX;j++){ 
                    isPrime[j*i] = 0; 
                } 
            } 
        } 

其中第一层循环中，i只需要循环到MAX的平方根就行，下面的if不能省，否则会重复判断。内层的for循环，j要从i开始，否则也会做重复工作，同时要保证i*j<MAX。