java-打印不大于N的质数

public class PrimeNumber {

	/**
	 * 寻找不大于N的质数
	 */
	public static void main(String[] args) {
		int n=100;
		PrimeNumber pn=new PrimeNumber();
		pn.printPrimeNumber(n);
		System.out.println();
		pn.printPrimeNumber2(n);
	}

	public void printPrimeNumber(int n){
		int i=2;
		while(i<=n){
			if(isPrimeNumber(i)){
				System.out.print(i+",");
			}
			i++;
		}
	}
	//Solution 1
	//it's not a good solution
	public boolean isPrimeNumber(int x){
		boolean re=true;
		for(int i=2;i*i<=x;i++){
			if(x%i==0){
				re=false;
				break;
			}
		}
		return re;
	}
	
	//Solution 2
	//i--> 2 to sqrt(n)
	//delete i*2,i*3.....i*sqrt(n)
	public void printPrimeNumber2(int n){
		boolean[] a=new boolean[n+1];
		for(int i=2;i<=n;i++){
			a[i]=true;
		}
		for(int i=2;i*i<=n;i++){
			for(int j=i;j*i<=n;j++){
				a[j*i]=false;
			}
		}
		for(int i=0;i<n;i++){
			if(a[i]){
				System.out.print(i+",");
			}
		}
	}
}

评论

1 楼 123048591 2012-01-15  

线性筛选素数