Miller_Rabin · 大数

Miller_Rabin · 大数

51nod 1186 质数检测 V2​ 在这个过程中犯了许多低级错误。哎，我的java基础啊。 相关知识点记录：

==比较的是对象的地址，也就是是否是同一个对象；

equal比较的是对象的值。

Math.random() 产生[0-1)的随机浮点数

util.Random:

Random()：创建一个新的随机数生成器。Random r=new Random();

int n = r.nextInt();  //生成-231到231-1之间的整数

生成[0,x)区间的整数：

int n2 = r.nextInt(x);

or

n2 = Math.abs(r.nextInt() % x);

嗯，其他就是写代码了。

import java.util.*;import java.math.BigInteger;public class Main { static BigInteger two=BigInteger.valueOf(2), one=BigInteger.ONE, zero=BigInteger.ZERO; static BigInteger quick_mod(BigInteger a,BigInteger m,BigInteger p){ BigInteger ans=one; a=a.mod(p); while(m.compareTo(zero)>0){ if(m.mod(two).equals(one))ans=ans.multiply(a).mod(p); a=a.multiply(a).mod(p); m=m.divide(two); } return ans; } static boolean Miller_Rabin(BigInteger p){ if(p.equals(two)) return true; if(p.equals(one)||p.mod(two).equals(zero)) return false; BigInteger m=p.subtract(one); int sum=0; while(m.mod(two).equals(zero)){ sum++; m=m.divide(two); } for(int i=0;i<10;i++){ int r=(int)(Math.random()*10000); BigInteger a=BigInteger.valueOf(r); if(a.compareTo(p)>0)a=a.mod(p); while(a.equals(zero)){ r=(int)(Math.random()*10000); a=BigInteger.valueOf(r); if(a.compareTo(p)>0)a=a.mod(p); } BigInteger x=quick_mod(a,m,p),g=zero; for(int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。