1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
| package challenge;
import java.util.Arrays; import java.util.Scanner;
public class LongRho {
//判定部分 //Miller_Rabin()算法素数判定 //是素数返回true.(可能是伪素数,但概率极小) //合数返回false; final static int S=20;//随机算法判定次数,S越大,判错概率越小 public static boolean millerRabin(long n){ if(n<2)return false; if(n==2)return true; if((n&1)==0) return false;//偶数 long x=n-1; long t=0; while((x&1)==0){x>>=1;t++;} for(int i=0;i<S;i++) { long a=(long) (Math.random()*(n-1)+1);//rand()需要stdlib.h头文件 if(check(a,n,x,t)) return false;//合数 } return true; }
//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数 //一定是合数返回true,不一定返回false static boolean check( long a, long n, long x, long t) { long ret=pow_mod(a,x,n); long last=ret; for(int i=1;i<=t;i++) { ret=mult_mod(ret,ret,n); if(ret==1&&last!=1&&last!=n-1) return true;//合数 last=ret; } if(ret!=1) return true; return false; } //计算 x^n %c public static long pow_mod( long x,long n, long mod)//x^n%c { if(n==1)return x%mod; x%=mod; long tmp=x; long ret=1; while(n!=0) { if((n&1)!=0) ret=mult_mod(ret,tmp,mod); tmp=mult_mod(tmp,tmp,mod); n>>=1; } return ret; } //计算 (a*b)%c. a,b,直接相乘可能溢出的 // a,b,c <2^63 public static long mult_mod( long a, long b, long c) { a%=c; b%=c; long ret=0; while(b!=0) { if((b&1)!=0){ret+=a;ret%=c;} a<<=1; if(a>=c)a%=c; b>>=1; } return ret; } //pollard_rho 算法进行质因数分解 static long factor[]=new long[100];//质因数分解结果(刚返回时是无序的) static int tol;//质因数的个数。数组小标从0开始
static long gcd( long a, long b) { if(a==0)return 1; if(a<0) return gcd(-a,b); while(b!=0) { long t=a%b; a=b; b=t; } return a; }
static long Pollard_rho( long x, long c) { long i=1,k=2; long x0=(long) (Math.random()*x); long y=x0; while(true) { i++; x0=(mult_mod(x0,x0,x)+c)%x; long d=gcd(y-x0,x); if(d!=1&&d!=x) return d; if(y==x0) return x; if(i==k){y=x0;k+=k;} } } static //对n进行素因子分解 void findfac( long n) { if(millerRabin(n))//素数 { factor[tol++]=n; return; } long p=n; while(p>=n)p=Pollard_rho(p,(long) (Math.random()*(n-1)+1)); findfac(p); findfac(n/p); } public static void main(String[] args) { System.out.println("please enter the number to be deal!"); Scanner s=new Scanner(System.in); String str3=s.next(); long n=Long.parseLong(str3); ; System.out.println(n+" is prime number or not?"); boolean flag=millerRabin(n); if (flag) { System.out.println("yes"); }else { System.out.println("no"); } findfac(n); if (!flag) { System.out.println("How to resolve this number:"); System.out.print(n+"="); for(int i=0;i<tol;i++){ if (i==tol-1) { System.out.print(factor[i]); }else{ System.out.print(factor[i]+"*");} } } }
}
|