我正在编写一种方法来检测BigInteger是否为素数.我使用以下代码/算法来检查给定数字是否为素数.但这是非常缓慢的,如果一个数字可以说长10个数字需要很长时间.
public boolean returnPrime(BigInteger testNumber){
int divisorCounter=1;
BigInteger index,i ;
for ( index= new BigInteger("2"); index.compareTo(testNumber) !=1; index=index.add(new BigInteger("1"))){
System.out.println(index);
for(i= new BigInteger("2"); i.compareTo(index) != 1; i=i.add(new BigInteger("1"))){
if((testNumber.mod(i).equals(BigInteger.ZERO) )){
divisorCounter++;
}
if(divisorCounter>2){
return false;
}
}
}
return true;
}
是否有更好的算法可以使用BigInteger素数？我在Stackoverflow中找不到与此相关的问题.如果您遇到过这样的问题,请告诉我,或者如果您对如何解决有所了解,那么您的想法将受到高度赞赏.
背景
当我偶然发现gcc trunk中的一个新优化(将是版本9.x)时,我正在使用c中的素数进行操作,该优化将模数比较优化为0整数乘法并使用幻数进行比较.换句话说x%prime==0就变成了x*Magic_mul<=Magic_cmp
_Bool mod(unsigned x){return x % Constant == 0;}
mod:
imul edi, edi, Magic_mul
cmp edi, Magic_cmp
setbe al
细节
基于看到asm输出,它对所有整数进行了这些优化(好吧,至少是素数)我将它们转换为十六进制以帮助查看模式,但目前还不是很明显.
//32bit examples for _Bool mod_n(unsigned x){return x%n==0;};
//note: parameter is unsigned but it becomes a signed multiply
x%3==0; // x*0xAAAAAAAB <= 0x55555555
x%5==0; // x*0xCCCCCCCD <= 0x33333333
x%7==0; // x*0xB6DB6DB7 <= 0x24924924
x%11==0; // x*0xBA2E8BA3 <= 0x1745D174
x%13==0; // x*0xC4EC4EC5 <= 0x13B13B13
x%17==0; // x*0xF0F0F0F1 <= 0x0F0F0F0F
x%19==0; // x*0x286BCA1B <= 0x0D79435E
x%23==0; // …可能重复:
最快的素数测试算法
非常感谢对C#中快速素性测试的示例代码的引用,最好使用BigInteger或其他可变大小类型.