java – 大数的素数因子化

发布时间：2020-12-15 02:06:16 所属栏目：Java 来源：网络整理

导读：我想找到小于10 ^ 12的大数的素数因子分解. 我得到了这段代码(在 java中)： public static ListLong primeFactors(long numbers) { long n = numbers; ListLong factors = new ArrayListLong(); for (long i = 2; i = n / i; i++) { while (n % i == 0) { fa

我想找到小于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;
    }

首先,上述算法的复杂性是什么？我很难找到它？

对于素数较大的数字来说,它也会太慢.

是否有更好的算法,或者如何优化这个算法？

解决方法

如果你想对许多大数进行分解,那么你可能最好先找到最多为sqrt(n)的素数(例如使用 Sieve of Eratosthenes).然后你必须只检查那些素数是否是因子而不是测试所有i< = sqrt(n).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!