Категорический список шаблонов разработки существуют? [закрытый]

Функция isPrime() вызывается слишком много раз в primefactors. Например, i == 2 и в n имеется много дивизоров 2. Верхний вызов (isPrime(i)) в порядке. Однако внутри цикла while (n % i == 0) вы проверяете isPrime(n) после каждого деления n /= 2;. Итак, если начальный n равен 100, функция isPrime() вызывается для 50 и следующего цикла для 25. В этом нет смысла. Я думаю, что это самая большая проблема здесь, так как даже если isPrime работает в линейном режиме, слишком много можно называть его много раз во внутреннем цикле.

Можно выйти из цикла для i в двух случаях: n равно 1 после делений или n для уверенного простого, если i больше sqrt(n).

public String primefactors(int n) {
    String factors = "";
    int max_divisor = sqrt(n);
    for (int i = 2; i <= max_divisor; i++) {
        if (isPrime(i)) {
            while (n % i == 0) {
                n /= i;
                if (n == 1)
                    factors = factors + Integer.valueOf(i).toString();
                else
                    factors = factors + Integer.valueOf(i).toString() + "*";
            }
            max_divisor = sqrt(n);
        }
    }
    // check for the last prime divisor
    if (n != 1)
        factors = factors + Integer.valueOf(n).toString();

    return factors;
}

Даже после этого улучшения (и sqrt(n) как максимальный предел в isPrime()), ваш алгоритм будет иметь линейную сложность O(n), так как для i существует не более sqrt(n) петель, а максимальное число зондов для prime в isPrime равно также sqrt(n).

Да, это можно сделать лучше, выбрав лучшие алгоритмы для isPrime(). Даже если вам не разрешено использовать жестко заданную таблицу простых чисел, можно создать такую ​​таблицу поиска во время выполнения (если памяти достаточно). Таким образом, можно использовать автоматически сгенерированный список простых чисел, организованных в порядке возрастания, чтобы исследовать заданное число до sqrt(n). Если i становится больше, чем sqrt(n), это означает, что следующее простое число найдено, и оно должно быть добавлено к таблице поиска, а isPrime() должно возвращать true.

Пример

Предположим, что isPrime вызывается для 113. В этот момент таблица поиска имеет список предыдущих простых чисел: 2,3,5,7,11,13.... Итак, мы пытаемся разделить 113 на элементы из этого списка до sqrt(113) (while (i <= 10)). После попытки 2,3,5,7 следующий элемент в списке 11 слишком велик, поэтому 113 добавляется в список простых чисел, а функция возвращает true.

Другие алгоритмы может дать лучшую производительность в худшем случае. Например, сито Эратосфена или сито Аткина можно использовать для эффективного предкомпьютерного списка простых чисел до заданного n с наилучшей сложностью O(n) для наилучшей реализации. Здесь вам нужно найти все простые числа до sqrt(n), поэтому для создания такого списка требуется O(sqrt(n)). После создания такого списка вам нужно попытаться разделить ваш ввод по номерам, это список, который занимает не более sqrt(n) зондов. Таким образом, сложность алгоритма - O(sqrt(n)). Однако предположим, что ваш вход 1024 равен 2 мощности 10. В этом случае первый алгоритм будет лучше, так как он не перейдет к простым числам, большим 2.

Вам действительно нужна функция isPrime ()?

С гибким мышлением Если мы посмотрим поближе, кажется, вам не нужно искать все простые числа в некотором диапазоне. Вам нужно было найти все простые делители одного заданного целого числа. Однако, если мы попытаемся разделить n на все целые числа в диапазоне до sqrt(n), что также является хорошим решением. Даже если такое целое число не является простым, оно будет пропущено из-за условия n % i == 0, так как все простые числа, меньшие, чем тестируемое целое число, уже удалены из n, так что простое модульное деление здесь совпадает с isPrime(). Полное решение с O(sqrt(n)) сложностью:

public String primefactors(int n) {
    String factors = "";
    int max_divisor = sqrt(n);
    for (int i = 2; i <= max_divisor; i++) {
        while (n % i == 0) {
            n /= i;
            max_divisor = sqrt(n);
            if (n == 1)
                factors = factors + Integer.valueOf(i).toString();
            else
                factors = factors + Integer.valueOf(i).toString() + "*";
        }
    }
    // check for the last prime divisor
    if (n != 1)
        factors = factors + Integer.valueOf(n).toString();

    return factors;
}

Также возможно разделить функцию, чтобы избежать проверки if (n == 1) во внутреннем цикле, однако это не меняет сложность алгоритма.