Miller_Rabin · 大数
发布时间:2020-12-14 02:05:46 所属栏目:大数据 来源:网络整理
导读:51nod 1186 质数检测?V2 http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1186 给出一个很大的数字N,2=N=10^30。判断他是不是素数。 分析:数字很大,使用java的BigInteger解决。 在这个过程中犯了许多低级错误。哎,我的java基础
51nod 1186 质数检测?V2 给出一个很大的数字N,2<=N<=10^30。判断他是不是素数。 分析:数字很大,使用java的BigInteger解决。 ==比较的是对象的地址,也就是是否是同一个对象; 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<sum;j++){ g=x.multiply(x).mod(p); if(g.equals(one)&&x.equals(one)==false&&x.equals(p.subtract(one))==false) return false; x=g; } if(g.equals(one)==false) return false; } return true; } public static void main(String[] args) { Scanner cin=new Scanner(System.in); BigInteger p=zero; while(cin.hasNext()){ p=cin.nextBigInteger(); if(Miller_Rabin(p)) System.out.println("Yes"); else System.out.println("No"); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |