Наибольший основной фактор:

Задача просит нас найти наибольший простой делитель большого числа 600851475143.

Для данного числа N мы будем исключать все степени его простых множителей, пока не уменьшим число N до 1. Устраняя степени простых множителей из N, мы продолжаем обновлять первичный множитель в переменной, чтобы в дальнейшем отслеживать наибольший простой множитель. на.

Как мы на самом деле это сделаем?
Мы будем перебирать возможные множители N, и если возможный множитель делит его, мы продолжим делить его от N, чтобы полностью исключить его силу. от N.
Таким образом мы гарантируем, что если мы переберем возможные множители в порядке возрастания, мы исключим степени простого числа N, и следующий делитель уменьшенного N будет следующим простым множителем.

Давайте рассмотрим примеры для некоторых значений N:

  • Если N = 90
    Мы перебираем возможные множители, здесь 2,3,4,5,6,and so on up to 90
    2 делит 90, поэтому мы продолжаем делить 90 на 2, пока оно не изменится. делится на 2.
    Остается N = 45 (у него была только одна степень 2)
    Теперь наши возможные множители: 3,4,5,6, and so on upto 45.
    3 делит 45 , поэтому мы продолжаем делить 45 на 3, пока оно не перестанет делиться на 3.
    Остается N = 5 (у него было две степени 3)
    Теперь, наши возможные множители равны 4 and 5
    4 не делит 5.
    5 делит 5, поэтому делите 5 на 5.
    Остается N = 1 (было только одно степень 5)
    Таким образом, в нашей последней обновленной переменной ответом будет 5 - наибольший простой множитель 90.
  • Если N = 27
    Мы перебираем возможные множители, здесь 2,3,4,5,6,and so on up to 27
    2 не делит 27, поэтому мы переходим к следующему возможному множителю.
    3 делит 27, поэтому мы продолжаем делить 27 на 3, пока оно не перестанет делиться на 3.
    Остается N = 1. (у него было три степени 3)
    Таким образом, в нашей последней обновленной переменной ответом будет 3 - наибольший простой множитель 27.

Анализ временной сложности:

  • Во внешнем цикле while i в худшем случае дойдет до N. Это будет так, когда N само является простым числом, а сложность будет O (N).
  • Во внутреннем цикле while i делит N до тех пор, пока больше не сможет делиться. Таким образом, в худшем случае i должен быть минимальным множителем для деления максимального времени. Следовательно, в худшем случае i будет 2, а N будет степенью 2, а сложность будет O (lg (N)).
  • Общая временная сложность составит O (N lg (N)).

Это хорошо для малых и средних-больших значений N.
Но для значений N, имеющих несколько степеней очень больших простых чисел, это значительно медленнее.

Можем ли мы его улучшить?

Утверждение:
Любое число N ›1 может иметь не более одного простого множителя больше √N

Доказательство от противного:

Мы знаем Фундаментальную теорему арифметики, которая утверждает,
Каждое положительное целое число n ›1 может быть представлено точно одним способом как произведение степеней простых чисел:

Мы предполагаем, что существуют два простых числа P₁ и P₂ такие, что P₁ | N и P₂ | N и P₁, P₂ ›√ N, со степенями n₁, n₂› 0

Поскольку, P₁, P₂ ›√ N, следовательно, P₁ * P₂› N.
Произведение двух простых чисел, делящих N больше N,
Следовательно, произведение их степеней очевидно больше N.
Таким образом, это нарушает Фундаментальную теорему арифметики.
Следовательно, наше предположение неверно и не может быть более одного простого делителя N (› 1) больше √ N.

Как мы можем использовать это утверждение, чтобы улучшить нашу временную сложность?
Мы будем перебирать множители N ≤ √N, поскольку теперь мы знаем, что только один простой множитель может быть больше √N.
Мы будем один за другим перебирать возможные множители ≤ √N, и если он делит N, мы удалим все степени этого множителя из N, и следующим возможным делителем уменьшенного значения N будет следующее простое число. фактор.
И поскольку мы повторяем только факторы ≤√N, может случиться так, что N не может быть полностью уменьшено до 1, как в предыдущем неэффективном подходе.

Случай 1:
Если мы повторили все множители до √N, а N по-прежнему не равно 1, то мы знаем, что все простые числа ≤√N полностью исключены и единственное простое число остается простое число ›√N, и, следовательно, уменьшенное значение N является наибольшим простым делителем N.

Случай 2:
Но есть и другой случай. Когда нет простого ›√N, N будет уменьшено до 1, и нам нужно отслеживать простые множители до сих пор, и последний из них будет наибольшим простым делителем N.

Возьмем те же примеры N, которые были взяты выше:

  • Если N = 90 (случай 1)
    Мы перебираем возможные множители, здесь 2,3,4,5,6,7,8,9
    2 делит 90, поэтому мы продолжаем делить 90 на 2, пока оно не делится на 2.
    Остается N = 45 (у него была только одна степень 2)
    Теперь наши возможные множители из 3,4,5,6.
    3 делит 45, поэтому мы продолжаем делить 45 на 3, пока оно не перестанет делиться на 3.
    Остается N = 5 (у него было две степени 3)
    Теперь нет возможных множителей, поскольку √5 = 2, а у нас уже были простые множители до 3.
    Осталось N = 5.
    Мы перебрали все простые множители. ≤ √5, но все же N не равно 1.
    Это означает, что у нас есть простой множитель больше √5, который является текущим значением N.
    Таким образом, ответ в N, последний обновлено 5 - наибольший простой множитель 90.
  • Если N = 27 (случай 2)
    Мы перебираем возможные множители, здесь 2,3,4,5.
    2 не делит 27, поэтому мы переходим к следующий возможный множитель.
    3 делит 27, поэтому мы продолжаем делить 27 на 3, пока оно не станет делиться на 3.
    Остается N = 1. (Было три степени 3)
    Мы перебрали все простые множители ≤ √27, и N = 1.
    Таким образом, ответ в нашей переменной, последнее обновление, будет 3 - наибольший простой множитель 27 .

Еще одна оптимизация (уменьшение постоянного коэффициента):
Мы знаем, что только четное простое число равно 2.
Итак, после 2 нам нужно проверить только нечетные множители для N.
Если мы позаботимся о 2 отдельно, то мы можем пропустить множители на 2.

Анализ временной сложности:
Общая временная сложность будет O (√N lg (√N)) с почти половиной постоянного множителя.



adzo261 / Project-Euler-Solutions
Решения для Project Euler с использованием Python 3 github.com



Не стесняйтесь комментировать сомнения или предложения.