JavaBig整数素数

BigInteger.probablePrime(bitLength, random) 将返回指定位长度的(可能的)素数。最大值为2 ^位长度-1,最小值为2 ^(位长度-1)。尽管我很讨厌它作为答案,但它可能是你最好的选择,除非你想开始钻研数论。

你要做的是计算出你的范围要求的位长度,然后把它们传递给 probablePrime() 直到你得到一个在正确范围内的素数。

如果你的比率max/min不接近1,jprete的答案是好的。

如果您的范围很窄,您的最佳选择可能是执行以下操作:

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

这个 density of primes 总的来说相当高,它基本上是对数(x)中的1,所以你不必重复太多次才能找到素数。(举个例子:10左右的数字 ^二十三 ,平均每52个整数中就有一个是素数。上面的代码只涉及每6个数字中的2个,所以您最终会为10个左右的数字平均循环17次。 ^二十三 )

只需确保有一个良好的素性测试,Java BigType就有一个。

作为对读者的练习,扩展上面的函数,以便它通过使用30k+x(模30,有22个模始终是复合的,只有8个模可能是素数)或210k+x提前筛选出更多的复合数。

编辑:参见 US patent #7149763 (OMFG!!!!)