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]+"*");}
}
}
}
}
|
