Попытки найти наибольший простой множитель

Question

Это происходит от 3 вопроса по проекту Эйлер .:

https://projecteuler.net/problem=3

Проблеме: простых множители 13195 являются 5, 7, 13 и 29. Что такое наибольший простой коэффициент числа 600851475143?

Потому что это головоломка, я бы предпочел не использовать консервированные методы Руби. Итак, вот оно ...

Текущая логика:
num - номер, который мы ищем для основных факторов.
кандидат является потенциальным основным фактором
SQRT квадратный корень из NUM

until candidate >= sqrt 

Я позаимствовал эту идею у Сита Эратосфена для нахождения простых чисел, где алгоритм проверяет делимости любого числа до площади корень из числа. кандидат - это номер для проверки, если num имеет делитель.

if num % candidate == 0 
... 
end 

Цель состоит в том, чтобы проверить, является ли num делимым на что угодно (имеет факторы). Если num не делится на кандидата, то кандидат будет увеличиваться на 1 до тех пор, пока оператор until не станет истинным или до тех пор, пока число не будет делено на кандидата.

Если число делится на кандидата, то мы знаем, что кандидат является простым и он вставлен в prime_factor. Затем рекурсия проверяется на новое число.

prime_factors << num 

Если цикл until верно, то, что Num НЕ имеет делитель и, следовательно, является простым. В результате он вставляется в prime_factors.

Издание:

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

Что должно произойти:
prime_factors = [2,2,19]
prime_factors.last = 19

Что происходит фактическое:
prime_factors = [2,2,19,19,38]
prime_factors.last = 38

весь код:

def largest_prime_factor(num,prime_factors) 
puts "beg fx: num: #{num}, prime_factors: #{prime_factors} 
candidate = 2 
sqrt = Math.sqrt(num) 
loop_count = 0 
until candidate >= sqrt 
    if num % candidate == 0 
    num = num/candidate 
    prime_factors << candidate 
    largest_prime_factor(num,prime_factors) 
    end 
    candidate += 1 
    loop_count +=1 
end 
    puts "outside loop: candidate >= sqrt is #{candidate >= sqrt} num: #{num}, prime_factors: #{prime_factors}, candidate: #{candidate}, sqrt: #{sqrt}, loop: #{loop_count}" 
    gets 
prime_factors << num 
prime_factors.last 
end 

Answer 1

Так выглядит л ike, как вы предположили, проблема заключается в логике рекурсии.

Просто потому, что вы вызываете функцию рекурсивно, это не означает, что «родитель» перестает работать - он просто сидит и ждет, пока «ребенок» закончит, а затем продолжит движение. Именно здесь происходит это «переполнение».Код на самом деле не перекошен, а заканчивается.

Вы можете видеть это в своем заявлении puts. Обратите внимание: после остановки цикла sqrt увеличивается, потому что скрипт теперь запускает родительский код, а не после того, как закончится рекурсивная часть (дочерняя).

Для исправления я сделал 2 вещи: 1. Создайте логическое значение, указывающее, что блок кода прошел через рекурсию. Если это так, запустите этот код, иначе ... запустите что-то еще. 2. Если кандидат не 2, то приращение на 2. Это пропускает тестирование всех четных чисел, кроме 2. Нет необходимости проверять другие четные числа, так как это не простое.

def largest_prime_factor(num,prime_factors,recursive) 
    candidate = 2 
    until candidate >= Math.sqrt(num) 
    recursive = false 
    if num % candidate == 0 
     num = num/candidate 
     recursive = true 
     prime_factors << candidate 
     largest_prime_factor(num,prime_factors,recursive) 
    end 
    break if recursive 
    candidate == 2 ? candidate += 1 : candidate += 2 
    end 
    prime_factors << num unless recursive 
    prime_factors.last 
end