Articles

Project Euler #3

In Golf, Project Euler, Ruby on May 13, 2009 by Matt Grande

Here’s the next one. I’m not happy with the way I determine if it’s a prime number (checking the modulo of every possible number), but it works.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

def find_largest_prime_factor(n)
  if n % 2 == 0
    find_largest_prime_factor(n/2)
  else
    x = find_divisor(n, 3)
  end
  puts x
end

def find_divisor(number, divisor)
  return divisor if divisor >= number
  if number % divisor == 0
    find_divisor(number/divisor, divisor)
  else
    find_divisor(number, divisor+2)
  end
end

find_largest_prime_factor(600851475143)

And the golf…

# Score: 98
def a n;p n%2==0?a(n/2):b(n,3);end;def b(n, d);d>=n ?d:n%d==0?b(n/d,d):b(n,d+2);end;a 600851475143
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: