大数的素因式分解
大数的素因式分解
提问于 2012-09-04 01:26:10
我想找出小于10^12的大数的素数分解。我得到了下面的代码(用java编写)：
public static List<Long> primeFactors(long numbers) {
long n = numbers;
List<Long> factors = new ArrayList<Long>();
for (long i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}首先，上述算法的复杂度是多少?？我很难找到它？？
而且，对于质数很大的数字来说，它也太慢了。
有没有更好的算法，或者怎么优化这个算法?？
回答 4
Stack Overflow用户
回答已采纳
发布于 2012-09-04 01:39:37
如果你想分解很多大数，那么你最好先找到最大到sqrt(n)的素数(例如使用Sieve of Eratosthenes)。然后，您只需检查这些质数是否为因子，而不是测试所有的i <= sqrt(n)。
Stack Overflow用户
发布于 2012-09-04 01:29:44
复杂性是O(sqrt(n))。在sqrt(n)之后检查数字是没有意义的。
这意味着对于10^12，它将花费最多的1 000 000迭代，这并不慢。
Stack Overflow用户
发布于 2012-09-04 01:53:13
大数的因式分解是一个困难的问题，这就是为什么加密算法使用大素数的因数来使加密难以破解的部分原因。
public static void main(String... args) {
int nums = 100;
for (int i = 0; i < nums; i++) {
long start = System.nanoTime();
primeFactors(Long.MAX_VALUE - i);
long time = System.nanoTime() - start;
if (time > 100e6)
System.out.println((Long.MAX_VALUE-i) + " took "+time/1000000+" ms.");
}
}
public static List<Long> primeFactors(long n) {
List<Long> factors = new ArrayList<Long>();
while (n % 2 == 0 && n > 0) {
factors.add(2L);
n /= 2;
}
for (long i = 3; i * i <= n; i+=2) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1)
factors.add(n);
return factors;
}打印
9223372036854775806 took 3902 ms.
9223372036854775805 took 287 ms.
9223372036854775804 took 8356 ms.
9223372036854775797 took 9519 ms.
9223372036854775796 took 1507 ms.
9223372036854775794 took 111 ms.
9223372036854775788 took 184 ms.如果您将Long.MAX_VALUE替换为1000000000000L，则它们都在20ms内进行因式分解。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12251962
复制相关文章
相似问题
腾讯云开发者
