eratosthenes.java

平方筛 验证质数的方法

/*
 * Created on May 19, 2004
 *
 * Simple implementation of the sieve of Eratosthenes
 */

/**
 * @author robert
 *
 * This class contains only static members. pi(n) returns the number of 
 * primes less or equal to n. 
 * Note that this program does not handle large n.  
 */
public class Eratosthenes {

	public static int pi(int n) {
		int sieve[] = new int[n-1];
		//initialize the sieve
		for (int k=1; k<n; ++k) {
			sieve[k-1] = k+1;
		}
		for (int k=0; k<Math.floor(Math.sqrt(n)); ++k) {
			while (sieve[k]==0) ++k;
			for (int l=2; l*sieve[k]-2<n-1; ++l) {
				sieve[l*sieve[k]-2] = 0;
			}
		}
		//finally count the elements in the sieve
		int count = 0;
		for (int k=0; k<n-1; ++k) {
			if (sieve[k]!=0) {
				++count; 
			}
		}
		return count;
	}
	
	public static void main(String[] args) {
		System.out.println("Pi(100000)="+pi(100000));
	}
}