Project Euler #3

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

Project Euler #2

Here we go, Project Euler #2!

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

one_back, two_back, current_fib, total = 1, 1, 0, 0</code>

while current_fib &lt; 4_000_000 do
two_back = one_back
one_back = current_fib
current_fib = one_back + two_back
total += current_fib if current_fib % 2 == 0
end

puts total

And the golf…

# Score: 69
a,b,c,t=1,0,0,0;while(c<4000000):b=a;a=c;c=a+b;t+=c if c%2==0;end;p t

EDIT!

I knew there was a way to do it without that stupid current_fib variable, but I couldn’t get it to work at first. Then, as soon as I post, I realised what I was doing wrong.

one_back, two_back, total = 1, 1, 0

while one_back < 4_000_000 do
  total += one_back if one_back % 2 == 0
  current = one_back
  one_back += two_back
  two_back = current
end

puts total

And, even better, it improved my golf score!

# Score: 63
a,b,t=1,1,0;while a<4000000:t+=a if a%2==0;c=a;a+=b;b=c;end;p t

Project Euler #1

I recently signed up for Project Euler. I’ve decided to see how far I can get, both just solving the problems and “golfing” them. If you’re not familiar with programming golf, it’s when you try to write as few lines of code and characters as possible.

So far, I’ve only solved the first problem, as I’ve just started. I’m looking forward to doing more in the future. If you’re interested, here’s my solution, along with my golf solution.

# If we list all the natural numbers below 10 that are
# multiples of 3 or 5, we get 3, 5, 6 and 9. The sum
# of these multiples is 23.
# Find the sum of all the multiples of 3 or 5 below 1000.

total = 0
1000.times do |i|
  if i % 3 == 0 or i % 5 == 0
    total += i
  end
end
puts total

# Score: 45
t=0;1000.times{|i|t+=i if i%3==0||i%5==0};p t