Java求n以内的所有质数

质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。

方法1：根据质数的定义求解；

方法2：对方法1作进一步优化，仅需判断到该数的平方根；

方法3：基于规律“除了2，所有的质数都是奇数；如果一个数不能被它之前的质数整除，那么这个数是质数”进一步优化程序。

示例程序如下：

package test;

import java.util.ArrayList;
import java.util.List;

public class FindPrime {

	public static void main(String[] args) {
		long time = System.nanoTime();
		System.out.println(findPrime1(10000).size());
		System.out.println(System.nanoTime() - time);

		time = System.nanoTime();
		System.out.println(findPrime2(10000).size());
		System.out.println(System.nanoTime() - time);

		time = System.nanoTime();
		System.out.println(findPrime3(10000).size());
		System.out.println(System.nanoTime() - time);
	}

	public static List<Integer> findPrime1(int n) {
		List<Integer> primes = new ArrayList<Integer>();
		primes.add(2);
		for(int i = 3; i <= n; i++) {
			for(int j = 2; j < i; j++) {
				if(i % j == 0)	break;
				if(j == i-1)	primes.add(i);
			}
		}
		return primes;
	}

	public static List<Integer> findPrime2(int n) {
		List<Integer> primes = new ArrayList<Integer>();
		primes.add(2);
		for(int i = 3; i <= n; i++) {
			int tmp = (int)Math.sqrt(i) + 1;
			for(int j = 2; j <= tmp; j++) {
				if(i % j == 0)	break;
				if(j == tmp)	primes.add(i);
			}
		}
		return primes;
	}

	public static List<Integer> findPrime3(int n) {
		List<Integer> primes = new ArrayList<Integer>();
		primes.add(2);
		for(int i = 3; i <= n; i+=2) {
			for(int j = 0; j < primes.size(); j++) {
				if(i % primes.get(j) == 0)	break;
				if(j == primes.size() - 1) { primes.add(i); break; }
			}
		}
		return primes;
	}

}

运行结果截图：

结果分析：

大家针对这个结果或许感到有点奇怪，为什么方法三会比方法二慢？虽然方法三理论上快点，但是方法三需要遍历list，而方法二不需要。除非当这个n特别大（我测到10^9，还是方法二优）时，不然方法二都是优于方法三的。所以我们认为最好的方法是：方法二 + 优化“除了2，所有的质数都是奇数”。