Ускорение величайших программ главного фактора в Рубине

Question

простой программа, чтобы найти наибольший простой множитель числа в Рубине, состоящий из 2-х способов:

def is_prime?(n) 
    (2..n).select {|number| n % number == 0}.length == 1 ? true : false 
end 

def prime_factors(number) 
    (1..number).select {|m| number % m == 0 && is_prime?(m) == true}.max 
end 

Это прекрасно работает для небольших количеств, как 100. Однако, Я пытаюсь решить проблему с Project Euler, которая использует номер 600851475143. При попытке этого проблема не будет работать, и я в конечном итоге отменяю ее примерно через минуту.

Как я могу изменить это, чтобы повысить производительность? Prime#prime_division метод

Answer 1

Используйте Руби:

require 'prime' 

Prime.prime_division(600851475143).max_by(&:first).first 
    #=> 6857 

Три шага:

a = Prime.prime_division(600851475143) 
    #=> [[71, 1], [839, 1], [1471, 1], [6857, 1]] 
    # Note (71**1)*(839**1)*(1471**1)*(6857**1) #=> 600851475143 
b = a.max_by(&:first) 
    #=> [6857, 1] 
b.first 
    #=> 6857 

Answer 2

Что касается вашего is_prime? метода:

1. Рубиновые конвенции предложить вам назвать его prime?, не is_prime?
2. Неправильно обрабатывает случаи, когда n является одним или менее
3. #select будет продолжать повторение после того, как оно нашло совпадение; для лучшей производительности он должен выйти из цикла как можно быстрее
4. Быстрой оптимизацией является возвращение ложным для любого числа, равномерно делится на два
5. вашего цикла может начаться в три, и только перебирать нечетные числа
6. Ваш цикл только должен итерацию до квадратного корня из n, вместо n

был недавно, аналогичное обсуждение, here, и я опубликовал гораздо быстрее prime? метод here.

Answer 3

Существует способ факторинга, который более эффективен и который также находит только простые факторы, устраняя необходимость проверки на грубость. Пройдите до конца, чтобы увидеть или прочитать, чтобы увидеть, как я туда попал.

Я реструктурировать свое решение, поэтому было бы легче думать о том, извлекая метод factors, удаляя ненужные явные использования булевых и переименования некоторых вещей:

def greatest_prime_factor(n) 
    factors(n).select { |c| prime?(c) }.max 
end 

def factors(n) 
    (1..n).select { |c| n % c == 0 } 
end 

def prime?(n) 
    (2..n).count { |c| n % c == 0 } == 1 
end 

Существует неэффективность в factors: даже после того, как знайте, что число c (для «кандидата») является фактором, мы тестируем числа больше n/c. Чтобы исправить это, когда мы находим коэффициент, разделите п на него, прежде чем мы посмотрим на следующий фактор:

def factors(n) 
    if n == 1 
    [] 
    else 
    f = (2..n).find { |c| n % c == 0 } 
    [f] + factors(n/f) 
    end 
end 

(. Другие методы остаются теми же) С этим изменением, вся программа факторов 600851475143 в несколько ms (не считая времени запуска процесса Ruby).

Почему это изменение так эффективно? Дело не только в том, что factors был медленным; оригинальная программа потратила около 75% своего времени в prime?. Но в то время как исходная версия factors вернула все числовые факторы, как простые, так и нестандартные, новая версия factors возвращает только числа.(Это связано с тем, что он накапливает наименьший оставшийся множитель, а наименьший первичный коэффициент всегда меньше наименьшего неферментного фактора.) Таким образом, мы не только сейчас факторизуем быстрее, но и имеем меньше факторов для проверки грубости, а также факторов, которые мы тестирование на грубость меньше и меньше времени для проверки на грубость.

Более того, так как factors теперь возвращает простые числа, мы не должны проверить первичность на всех, так что давайте переименовать factors, чтобы понять, что она возвращает простые числа и устранить prime?:

def greatest_prime_factor(n) 
    prime_factors(n).max 
end 

def prime_factors(n) 
    if n == 1 
    [] 
    else 
    f = (2..n).find { |c| n % c == 0 } 
    [f] + prime_factors(n/f) 
    end 
end 

Как быть короче, это еще быстрее, факторинг 600851475143 менее чем за 1 мс (опять же, не считая времени запуска Ruby) на моей машине.