Ruby Prime Factors

Question

Я видел решения, размещенные на других языках, но не Ruby, поэтому я спрашиваю здесь.

Пытаясь выяснить, наибольший первичный фактор 13195.

Мой код выглядит следующим образом

# find out all numbers that divide without remainder into 13195 

    array = [] 
    count = 2 

    13195.times do 
     if 13195 % count == 0 
      array.push(count) 
     end 
     count += 1 
    end 



    #From those numbers that divide cleanly into 13195, find out which are prime aka can only be divided by themselves and 1 

    new_count = 2 
    primes = 0 

    array.each do |x| 
     while new_count < x 
      if x % new_count != 0 
      else 
       if x > primes 
       primes = x 
      end 
      end 
     new_count += 1 
     end 
    end 

    puts primes 

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

Это вторая часть моего решения, которая является проблемой внутри каждого моего заявления, может кто-то указать мне в правильном направлении?

Answer 1

Ваш второй цикл может быть переписан, чтобы делать то, что должен делать.

Как я понимаю, ваша цель - выбрать из array, самый большой из таких элементов, которые являются первичными (делит только на 1 и на себя). Другими словами, элемент x имеет право, если он не делится на любое число между 2 и x-1.

result = array.select {|x| not (2..x-1).any? {|i| x % i == 0} }.max 
#=> 29 

---

В настоящее время логика имеет некоторые недостатки. Он не сбрасывает значение new_count и, следовательно, вы получаете неправильные результаты. Вот исправленная версия:

array.each do |x| 
    is_prime = true 
    while new_count < x 
     if x % new_count == 0 
      is_prime = false 
     end 
     new_count += 1 
    end 
    new_count = 2 
    primes = x if is_prime and x > primes 
end 

Answer 2

Я предлагаю вам использовать Prime#prime_division:

require 'prime' 

def largest_prime_factor(n) 
    Prime.prime_division(n).max_by(&:first).first 
end 

largest_prime_factor(13195) 
    #=> 29 

(1..1000).to_a.sample(15).sort.each {|n| puts "%3d: %3d" % [n, largest_prime_factor(n)]} 
61: 61 
80: 5 
88: 11 
250: 5 
304: 19 
414: 23 
514: 257 
548: 137 
679: 97 
716: 179 
754: 29 
770: 11 
906: 151 
907: 907 
968: 11 

Например,

n = 13195 
a = Prime.prime_division(n) 
    #=> [[5, 1], [7, 1], [13, 1], [29, 1]] 
b = a.max_by(&:first) 
    #=> [29, 1] 
b.first 
    #=> 29 

Оказывается, что элементы массива, возвращаемого prime_division в порядке увеличивая первичный коэффициент. Если это было гарантировано, можно просто написать:

Prime.prime_division(n).last.first 

max_by Я использовал в том случае, если порядок этих элементов является реализацией.

Answer 3

Сокращенный вариант:

require 'prime' 
primes = Prime.each(13195).to_a 
upper = primes.last 

primes будет иметь все простые числа от 0 до 13195 и верхней, очевидно, последней.

Answer 4

Я установил лимит простых чисел до 100000 (чтобы избежать от нескольких дней расчета больших чисел, как 600851475143 =))

def prime_factors(n) 
    prime_array = []  
    p = 2 
    if n < 2 
     return p 
    end 


    while p < n && p < 1000000 
    if n % p == 0 
     prime_array.push(p) 
    end 
    p +=1 
    end 

    primes = [] 

    prime_array.size.times do |i| 
    if n > 1 
     n = n/prime_array[i] 
     primes.push(prime_array[i]) 
    end 
    end 
    return primes.last 
end 

#prime_factors(600851475143) 
puts prime_factors(600851475143) 

#prime_factors(13195) 
puts prime_factors(13195)