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

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

0 голосов
/ 03 мая 2018

Я попытался найти наибольший простой множитель числа 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]
    }
}

1 Ответ

0 голосов
/ 03 мая 2018

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

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

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

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

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

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

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

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

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

...