Tag Archives: factorization

Euler Problem 124 – Prime Factors

When I was looking for a picture to represent Prime Number Factorization, I had no idea what to use. So I Googled images on the topic and discovered there was a Star Trek: Voyager episode called Prime Factors. The above picture is a scene from it — exciting I know! 😉 Too bad its not a picture of Seven of Nine.

So my solution consist of two parts. A prime number generator. I re-used the code from my solution of Euler Problem 131. The other part is a factorization routine that matches against the list of prime numbers. I found some concise Haskell code here.

This routine runs in less than 4 seconds on a single core 3 Ghz system.

import Data.List
import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m] where
    sieve [] = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..m])

primeFactors :: Integer -> [Integer]
primeFactors x = 
	unfoldr findFactor x where
		first (a,b,c) = a
		findFactor 1 = Nothing
		findFactor b = (\(_,d,p)-> Just (p, d))
			$ head $ filter ((==0).first) 
			$ map (\p -> (b `mod` p, b `div` p, p)) $ primes 100000

rad :: Integer -> Integer
rad n = product $ Data.List.nub $ primeFactors n

main = print $ snd $ sort [(rad x, x) | x <- [1..100000]] !! (9999)

Ah, what the heck — Why not?