Skip to content

Learning Scheme: Euler Problem 3

Been a long time since I last posted; real life has a way of getting in the way. The past few months read like the back cover of A Series of Unfortunate Events: if you don't want to hear about a thwarted move, a house fire, 2 graduations, negotiations for a new job and a carrot salad with lots of garlic, then you should put this down and live someone else's life.

But I'm not complaining; everything looks like it's working out well.

Going back to Scheme, the next Project Euler problem is:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

And straightforwardly:

(define gpf ; greatest prime factor
  (lambda (n try) ; n is the number to find the factor of; try is the lowest number to try
      ((> try (sqrt n)) n) ; no need to try a factor higher than the square root; if we get here, n is prime
      ((divides try n) (gpf (/ n try) try)) ; divide out the current trial factor and try again
      (else (gpf n (+ try 1))))))
(define euler3
  (lambda (n) (gpf n 2)))

(euler3 600851475143) gives us the answer 6857 pretty quickly.

But this is getting boring; I'm not using the interesting parts of Scheme. This sort of problem cries out for a prime number generator, and that cries out for call-with-current-continuation, and that cries out for some more playing and learning. I'll see what I can do.

Post a Comment

Your email is never published nor shared. Required fields are marked *