Java BigInteger素数
我正在尝试生成BigInteger类型的随机素数，即我提供的最小值和最大值之间。
我知道BigInteger.probablePrime（int bitlength，random），但我不确定比特长度是如何转换为输出素数的最大值/最小值。
谢谢，Steven1350
BigInteger.probablePrime(bitLength, random)将返回指定位长的（可能）素数。 这转换为最大值2 ^ bitlength – 1和最小值2 ^（bitlength – 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);
素数的密度总体上相当高，基本上是log（x）中的1，所以你不必重复太多次来找到素数。 （举个例子：对于10 23左右的数字，平均每52个整数中就有一个是素数。上面的代码只有6个数字中的2个，所以你最终会平均循环17次数字大约10 23。 ）
只要确保你有一个很好的素性测试，Java BigInteger就有一个。
作为读者的练习，扩展上述function，以便通过使用30k + x（模30，有22个总是复合的模，剩下8个可能是素数）或者210k，提前过滤出更多的复合数。 + x。
编辑：另见美国专利＃7149763 （OMFG !!!）