偶尔发现,但很实用,官方的求素数的方法

以前老是为求素数发愁,不管怎么做,效率总是不高.

今天为求一个数的阶乘而使用了BigInteger.本来想找一下BigInteger中输出科学计数格式的方法,没想到偶尔看到了:

 

public BigInteger

nextProbablePrime

()

返回大于此 BigInteger 的可能为素数的第一个整数。此方法返回的数是合数的概率不超出 2^-100 。此方法在执行以下搜索时将始终不会跳过素数：如果它返回 p ，则不存在 this < q < p 的素数 q 。

返回：

返回大于此 BigInteger 的可能为素数的第一个整数。

抛出：

ArithmeticException - this < 0 。

从以下版本开始：

1.5

简直不敢相信,众里寻他千百度,蓦然回首那人却在灯火阑珊处.赶快测试一下,求100以内的素数:

 

	public static void main(String[] args) {
		BigInteger bi = BigInteger.ZERO;
		while (true) {
			bi = bi.nextProbablePrime();
			if (bi.intValue() > 100) {
				break;
			}
			System.out.print(bi + " ");
		}
	}

 

 

快速运行完毕:

输出:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

我等算法薄弱人士的福音啊.

miller-rabin test
  the DSA spec (NIST FIPS 186-2)

http://www.cnblogs.com/feature/articles/1824667.html