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 教师闺蜜祝福语简短