Более эффективный способ поиска наибольшего простого множителя числа 600851475143

Question

Я попытался найти наибольший простой множитель числа 600851475143 и преуспел с помощью приведенного ниже кода, но я знаю, что это жестокий силовой путь, и, вероятно, есть более эффективный и элегантный способ решения этой проблемы. Тем не менее, я не мог думать ни о чем сразу и надеялся, что кто-то может поделиться своими решениями с объяснением.

public class Solution {

    // find prime numbers
    ArrayList<Long> primelist = new ArrayList<>();

    ArrayList<Long> findPrime(Long num) {
        for (Long i = Long.valueOf(2); i <= num; i++) {
            if (num % i == 0) {
                primelist.add(i);
                num = num / i;
                if (num == 1) {
                    break;
                }
            }
        }
        System.out.println(primelist);
        return primelist;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.findPrime(Long.valueOf(600851475143L)); // [71, 839, 1471, 6857]
    }
}

Answer 1

Если число, которое вы пытаетесь разложить на множители, является произведением двух больших простых чисел, то разложение на множители требует больших затрат. Однако ваш алгоритм (как вы заметили) особенно неэффективен.

• Ваш алгоритм известен как пробное деление, и это O(N), как вы его написали. Его можно легко улучшить до алгоритма O (N ^0,5) вхудшем случае; увидеть ниже.

• Существует несколько лучших алгоритмов различной сложности, обобщенных на этой странице Википедии: см. https://en.wikipedia.org/wiki/Integer_factorization.

• Известно, что проблема факторизации произвольного непростого числа находится в NP, и, как предполагается, ее нет в P: см. https://en.wikipedia.org/wiki/NP_(complexity).

---

Вот несколько простых способов ускорить вашу программу:

1. Не использовать Long для ваших расчетов. использование long вместо. Ваш код будет генерировать и собирать мусор в большом количестве Long объекты.

2. При использовании пробного деления для разложения числа n, вы можете перестать искать основные факторы, когда вы получите sqrt(n),

3. Когда вы найдете главный фактор, вы можете ускорить факторизацию, разделив исходное число на фактор, а затем попытаться факторизовать результат. (На самом деле, вы уже делаете это.)

(Но это "куриный корм" по сравнению с более сложными алгоритмами.)