[ Ruby Prime Factors ]

I've seen solutions posted in other languages but not Ruby so I'm asking here.

Trying to find out the largest prime factor of 13195.

My code is as follows

    # 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

In my first loop I am populating an empty array with all the numbers that divide into 13195 without a remainder, from testing this piece of code seems to be working.

It's the second part of my solution that's the problem inside my each statement, can someone point me in the right direction?

Answer 1

---

I suggest you use 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

For example,

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 

It appears that the elements of the array returned by prime_division are in order of increasing prime factor. If that were guaranteed, one could just write:

Prime.prime_division(n).last.first

I used max_by in the event that the order of those elements is implementation-specific.

Answer 2

---

Shorter version:

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

primes will have all primes from 0 to 13195 and upper obviously the last.

Answer 3

---

Your second loop can be re-written to do what is meant to do.

As I understand, your goal is to select from array, largest of such elements that are prime (divides by only 1 and itself). In other words, an element x is eligible if it is not divisible by any number between 2 and x-1.

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

---

Currently, your logic has some flaws. It is not resetting the value of new_count and hence you are getting wrong results. Here is corrected version:

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