Euler 3 Just Got Lisped Up

“What is the largest prime factor of the number 600851475143?”

One thing I’ve learned so far from the euler stuff is that if seems too hard, I’m doin’ it rong. What I initially did is go from 2, tried to find any prime number that is a factor 60085…3, and keep updating the highest found. This was silly. In reality, I needed to start from 60085…3, find the largest factor of it, and keep going if it’s not a prime number. After all, the highest possible factor can’t be higher than 60095..3/2, prime or not. If that fails, then increase the divisor by one, and check if the other number is a prime.

600851475143 / n = x where n 2 -> ?
600851475143 / 2 = x
600851475143 / 3 = x
600851475143 / 4 = x

This meant I needed two parts, one to roll through all possible values of n until x was a prime.

(defun lowest-prime-divisor (start &optional (current 2))
  (if (and (= 0 (mod start current)) (is-prime-number (/ start current)))
    (/ start current)
    (lowest-prime-divisor start (+ current 1))))

As I wrote before, this is taking the original number (6800??adf…3), and start with dividing it by 2. What ever the remainder is, take it and check if it’s a prime. If so, return that. If not, divide by 3. I have no clue why I named it lowest-prime-number. Probably a case where my limitless intellect is proving that I am not nearly smart enough to understand it.

Here is the brute force prime number check. Essentially start a 2, use mod, and increase the iteration. This is done until either something mod iteration is 0, or the iteration is the same as the number being checked. It has a special kind of ugliness, and inefficiency.

(defun is-prime-number (start &optional (currentDivisor 2))
  (if (= start currentDivisor)
      T
      (if (= 0 (mod start currentDivisor))
          nil
          (is-prime-number start (+ currentDivisor 1)))))

And I don’t have a macro this time. Mostly because I’m on 8 currently, and this is only the third post.