# Problem 35 - Prime factors

## Solution 1

Use the Sieve of Eratosthenes to find primes, then test each prime from lowest to highest.

``````import Html
import List
import Maybe

primeFactors : Int -> List Int
primeFactors n =
List.reverse <| factors n (primes n) []

factors : Int -> List Int -> List Int -> List Int
factors n ps acc =
case ps of
[] ->
acc

x :: xs ->
if n == x then
x :: acc
else if n % x == 0 then
factors (n // x) ps (x :: acc)
else
factors n xs acc

-- find all primes up to n

primes : Int -> List Int
primes n =
if n < 2 then
[]
else
eratos (List.range 2 n) []

-- sieve of Eratosthenes
-- remove all the the non-primes from a list

eratos : List Int -> List Int -> List Int
eratos candidates primes =
case candidates of
[] ->
List.reverse primes

x :: xs ->
let
cs =
List.filter (\y -> (y % x) /= 0) xs
in
eratos cs (x :: primes)
``````

## Solution 2

We can optimize the first solution by eliminating primes between n/2 and n.

``````primeFactors : Int -> List Int
primeFactors n =
if n < 2 then
[]
else
List.reverse <| factors n ((primes (n // 2)) ++ [ n ]) []
``````

## Solution 3

Faster still, use `dropWhile` to sieve the prime numbers for you

``````primeFactors : Int -> List Int
primeFactors n =
if n < 2 then
[]
else
let
prime =
Maybe.withDefault 0
<| dropWhile (\x -> n % x /= 0) [2..n]
in
prime :: (primeFactors <| n // prime)

dropWhile : (a -> Bool) -> List a -> List a
dropWhile predicate list =
case list of
[] ->
[]

x :: xs ->
if (predicate x) then
dropWhile predicate xs
else
list
``````