# Ruby Prime Factors

TAGS :
Viewed: 3 - Published at: a few seconds ago

#### [ 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 &lt; x
if x % new_count != 0
else
if x &gt; 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?

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.

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.

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
``````