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

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

今天为求一个数的阶乘而使用了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

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

评论

2 楼 kimmking 2010-11-10  

<div class="quote_title">i2534 写道</div>
<div class="quote_div">
<p>以前老是为求素数发愁,不管怎么做,效率总是不高.</p>
<p>今天为求一个数的阶乘而使用了BigInteger.本来想找一下BigInteger中输出科学计数格式的方法,没想到偶尔看到了:</p>
<p> </p>
<pre>public <a title="java.math 中的类" href="/admin/java/math/BigInteger.html">BigInteger</a>

<strong>nextProbablePrime</strong>

()</pre>
<dl>
<dd>返回大于此 <code>BigInteger</code> 的可能为素数的第一个整数。此方法返回的数是合数的<span style="color: #ff0000;">概率不超出 2^-100</span> 。此方法在执行以下搜索时将始终不会跳过素数：如果它返回 <tt>p</tt> ，则不存在 <tt>this &lt; q &lt; p</tt> 的素数 <tt>q</tt> 。 </dd>
<dd></dd>
<dd><dl>
<dt>
<strong>返回：</strong> </dt>
<dd>返回大于此 <code>BigInteger</code> 的可能为素数的第一个整数。 </dd>
<dt>
<strong>抛出：</strong> </dt>
<dd>
<code><a title="java.lang 中的类" href="/admin/java/lang/ArithmeticException.html">ArithmeticException</a> </code>- <tt>this &lt; 0</tt> 。 </dd>
<dt>
<strong>从以下版本开始：</strong> </dt>
<dd>1.5 </dd>
</dl></dd>
</dl>
<p>简直不敢相信,众里寻他千百度,蓦然回首那人却在灯火阑珊处.赶快测试一下,求100以内的素数:</p>
<p> </p>
<pre name="code" class="java"> public static void main(String[] args) {
BigInteger bi = BigInteger.ZERO;
while (true) {
bi = bi.nextProbablePrime();
if (bi.intValue() &gt; 100) {
break;
}
System.out.print(bi + " ");
}
}</pre>
 
<p> </p>
<p>快速运行完毕:</p>
<p>输出:</p>
<p>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 </p>
<p>我等算法薄弱人士的福音啊.</p>
</div>
<p> </p>
<p> </p>

1 楼 kimmking 2010-11-10  

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

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