我正在为 Android 设备开发一个小型素数应用程序,快完成了,但是我需要一些帮助来优化我的因式分解类。
我仍然遇到一两个问题,一些大数(偶数)在合理的时间内被分解。我认为我无法将 Eratosthenes 的筛子用于这个特定项目,因为我最多只能筛出 1000 万,而应用程序不会在我的物理设备(Samsung Galaxy S4 Mini)上崩溃。所以我的解决算法如下。我不确定我是否可以使我实现的 Pollard Rho 算法变得更好。
一旦确定要测试的数字不是素数或不是素数平方,我会快速进行最多 10 000 的试验除法,之后如果数字仍未完全因式分解,我将使用 Pollard Rho方法来减少它的剩余部分。
我希望能够分解 2 > 2^64 范围内的数字。
这是一个大约需要 15 秒的数字示例 256332652145852
它的因式分解是 [2, 2, 1671053, 38348971]。
如有任何帮助,我们将不胜感激。
try {
long num = Long.valueOf(input);
if(num == 1) {
return "1" + " = " + input;
} else if(num < 1) {
return "Cannot factor a number less than 1";
} else if(PrimeNumbers.isPrime(num) == true) {
return result = num + " is a Prime Number.";
} else if(isSquare(num) == true && PrimeNumbers.isPrime((long) Math.sqrt(num)) == true) {
return result = (int) Math.sqrt(num) + "<sup><small>" + 2 + "</small></sup>" + " = " + input;
} else {
factors(num, pFactors);
return result = exponentialForm(pFactors, num) + " = " + input;
}
} catch(NumberFormatException e) {
return result = "Unfortunately the number entered is too large";
}
}
public static void factors(long n, ArrayList<Long> arr) {
long number = trialDiv(n, arr);
if(number > 1) {
while(true) {
long divisor = pollard(number, 1);
if(PrimeNumbers.isPrime(divisor) == true) {
number /= divisor;
arr.add(divisor);
if(PrimeNumbers.isPrime(number) == true) {
arr.add(number);
break;
}
}
}
}
}
private static long trialDiv(long n, ArrayList<Long> arr) {
while(n % 2 == 0) {
n /= 2;
arr.add((long) 2);
}
for(long i = 3; i < 10000; i += 2) {
if(PrimeNumbers.isPrime(i) == true) {
while(n % i == 0) {
arr.add(i);
n /= i;
}
}
}
if(PrimeNumbers.isPrime(n) == true) {
arr.add(n);
return 1;
}
return n;
}
public static long pollard(long n, long c) {
long x = 2;
long y = 2;
long d = 1;
while (d == 1) {
x = g(x, n, c);
y = g(g(y, n, c), n, c);
d = gcd(Math.abs(y - x), n);
}
if (d == n) {
return pollard(n, c + 1);
} else {
return d;
}
}
static long g(long x, long n, long c) {
long g = (((x * x) + c) % n);
return g;
}
static long gcd(long a, long b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
最佳答案
您的 pollard 函数还可以,但不是很好。您正在使用 Pollard 的原始算法,但最好使用 Brent 的变体。但这可能不是您表现不佳的根源。
您的试用版功能很慢。检查每个可能的除数的素数是非常昂贵的,而且没有必要。除以复合数并不重要;除法总是会失败,但您不要浪费时间检查素数。更好的方法是轮分解。
关于android - Android 中的质因数分解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27668661/