prime.java

java 实现的一些算法： 赛选法求素数

package daniel.number_theory;

/**
 * 筛选法球素数
 * @author Daniel Cao
 *
 */
public class Prime {

	public static final int MAX_SIZE = 1000;

	public static boolean[] p = new boolean[MAX_SIZE];

	public static boolean isPrime(int n) {
		int t = (int) Math.pow(n, 0.5);
		for (int i = 2; i <= t; i++) {
			if (n % i == 0)
				return false;
		}
		return true;
	}

	public static void prime() {
		for (int i = 0; i < MAX_SIZE; i++) {
			p [i] = true;
		}
		p[1] = false;
		for(int i=2;i<MAX_SIZE;i++){
			if(p[i]){
				int j = i*i;
				while(j < MAX_SIZE ){
					p[j] = false;
					j += i;
				}
			}
		}
	}

	public static void main(String[] args) {
		prime();
		for(int i =0;i<100;i++){
			if(p[i]){
				System.out.println(i);
			}
		}
		System.out.println(p[3*5*7]);
	}
}