Algorithms in Ruby: Largest Prime Factor

  • The prime factors of 13195 are 5, 7, 13 and 29. The largest prime factor in this case is 29.
  • What is the largest prime factor of the number 600851475143 ?
If we want the largest prime multiple of 10, and the first prime number is 2, and when divided, is 5, with no remainder. Then, next prime multiple is 5. If we take the quotient of 5 and divide it by the prime multiple, 5, we get 1. Therefore, we have found the largest, but also the last prime number that will satisfy. Stop doing work, and return that last prime.
def lpf(n)   p Prime.prime_division(n)endlpf(600851475143)# prints: [[71, 1], [839, 1], [1471, 1], [6857, 1]]
def lpf(n)p Prime.prime_division(n).last[0]endlpf(600851475143)#prints: 6857

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
aaron feingold

aaron feingold

web developer making apps for people with appetite