Обзор
В третьей задаче проекта Эйлера вам предлагается разложить большое целое число, чтобы найти его наибольший простой множитель. Звучит достаточно просто. Тем не менее, мне потребовалось четыре дня и вдвое больше часов, чтобы пройти через несколько подходов, прежде чем я наконец получил ответ. К сожалению, это не похоже на победу, потому что мне пришлось выполнять чужой код Python. Я преобразовал его из Python 2.7 в 3.6 с помощью этого инструмента. Затем я сохранил его как локальный скрипт Python и запустил с помощью Anaconda IDE, получив ответ менее чем за полсекунды.
Этот ответ позволил мне открыть форум, чтобы увидеть другие варианты и официальный псевдокод, который я преобразовал в сценарий R и запустил за 0,24 секунды. Раздражающе быстро по сравнению с теми вещами, которые я пробовал, но они потерпели неудачу.
Вещи, которые не сработали
Первое, что я попробовал, это создать цикл while для всех ответов на целочисленные делители. Затем я удалил ответы, которые не были простыми. Это было и неэффективно, и не работало. Я продолжал сталкиваться с проблемами, когда он удалял основные ответы в тестовых последовательностях, которые я запускал. Я попытался пробежаться в понедельник утром и через 11 минут прошел менее 0,00009% пути.
Моя следующая стратегия состояла в том, чтобы попытаться создать список простых чисел, на которые нужно разделить проверочное число и посмотреть, даст ли оно мой ответ. Готовые списки, которые я нашел, были неправильно отформатированы для использования в качестве списков в R, и я не хотел тратить время на их очистку. Я попытался использовать пакет для создания списка до числа, которое я проверял. Пакет не смог вычислить достаточно большие простые числа для этой попытки. Это было на несколько порядков меньше.
Я попробовал еще раз с той же концепцией деления на простые числа, на этот раз с использованием циклов for. Однако эти циклы не были расчетными. Я не уверен, то ли я просто пропустил один или два символа при написании циклов, то ли они были ошибочными с самого начала. Несмотря ни на что, они не работали.
Объяснение того, что сработало
Во вступлении я ссылался на чей-то код Python, который наконец-то дал мне ответ. Я также преобразовал официальный псевдокод в свой ответ, который вы можете увидеть здесь. Преобразованный в R псевдокод работает следующим образом:
Начните с исследуемого числа (N). Запустите цикл if, проверяющий, равен ли модуль N/2 нулю. Если это так, сохраните N как N/2. Обновите рабочую переменную последнего рабочего фактора, чтобы она была равна 2. Пока модуль N/2 по-прежнему равен 2, продолжайте обновлять N с помощью N/2.
Если модуль N/2 не равен нулю, рабочая переменная последнего рабочего фактора теперь равна 1.
Двигаясь дальше, обновите другой рабочий коэффициент до 3.
Пока N больше единицы, если модуль N, деленный на этот новый фактор (коэффициент), равен нулю, обновите N, чтобы оно стало N/фактор. Обновите последний рабочий коэффициент равным коэффициентом. В то время как модуль N, деленный на этот коэффициент, равен нулю, обновите N, чтобы он стал N/фактор [этот вариант кажется немного лишним, но он работает, поэтому я сохранил его].
Обновите фактор, чтобы он был фактором + два (так что вы пропускаете непростые числа).
После завершения полного цикла отобразите последнее значение рабочего фактора.
Уроки выучены
Борясь с этой проблемой в течение нескольких дней, я обнаружил, что существует множество возможных путей к ответу. Самый оптимальный может оказаться не первым попавшимся путем. Я узнал о пакете, чтобы помочь поддерживать воспроизводимость, хотя я все еще учусь и на этом. Я также узнал, что некоторые из них могут занять некоторое время, чтобы понять.
Я начертил один из рабочих списков, чтобы увидеть, следует ли он различимой схеме, которую я, вероятно, продолжу в последующих задачах. Короткий ответ: да, это следует шаблону. Длинный ответ: да, шаблон не особенно полезен. Чтобы извлечь из этого что-то полезное, нужно еще поработать.
Для будущих тупиков я буду публиковать свой прогресс в Твиттере каждый день, когда работаю над ним. Я буду создавать частичные сообщения каждое следующее воскресенье, если я все еще работаю над этим.
Первоначально опубликовано на https://davidmvermillion.com 9 января 2021 г.
