Java中素数分解的Pollard Rho算法
它是对给定整数执行因式分解的算法。以下是实现Rho算法进行素因分解的程序。
程序
public class PollardsRho {
int num = 65;
public int gcd(int a, int b) {
int gcd = 0;
for(int i = 1; i <= a || i <= b; i++) {
if( a%i == 0 && b%i == 0 ) {
gcd = i;
}
}
return gcd;
}
int g(int x) {
return ((x*x)-1) % num;
}
public static void main(String args[]) {
PollardsRho obj = new PollardsRho();
int x = 2, y = 2, d = 1;
while(d==1) {
x = obj.g(x);
y = obj.g(obj.g(y));
d = obj.gcd((x - y), obj.num);
}
if (d == obj.num) {
System.out.println("Cannot calculate GCD for this element");
} else {
System.out.println("One of the divisors of given number is "+d);
}
}
}输出结果
One of the divisors of given number are 5
热门推荐
10 圣诞祝福语简短小学
11 祖国七十华诞简短祝福语
12 老师送的祝福语简短
13 生日祝福语大全女生简短
14 祝女性生日祝福语简短
15 牛年女神节祝福语简短
16 情人表白祝福语简短大气
17 老公开业祝福语简短
18 官宣新年祝福语简短