Problem 003: Largest Prime Factor

From Project Euler:

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

What is the largest prime factor of the number 600851475143 ?

This is the first problem with primes. There are some good ways to find primes, however for this simple problem we'll use a simple solution. First, let's define a function that tells us if a number $n$ is prime. The way it works is it will test every number $i$ from 2 to $\sqrt{n}$ to see if $n$ is divisible by $i$. If it is, then $n$ is not prime. We only need to go up to $\sqrt{n}$ because all non-prime numbers will have at least one factor between 2 and their square root.

(defn is-prime? [n]
  (->> (range 2 (int (Math/ceil (Math/sqrt n))))
       (some #(== (mod n %) 0))
       (not)))

From here, we can now filter through and find divisors of 600851475143, and figure out which is the maximum.

(def N 600851475143)

(println
  (->> (range 2 (int (Math/ceil (Math/sqrt N))))
       (filter #(== (mod N %) 0))
       (filter is-prime?)
       (apply max)
       ))

This gives us the correct result (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 3.clj
6857

real 0m1.651s
user 0m3.232s
sys 0m0.138s

There are more efficient ways to find primes: one good one to use is a prime sieve. We don't really need that for this problem since the number is fairly small, but for more advanced problems later on we'll want to use that approach.