Problem 12

Problem 12
Filename: prob12.hs

--The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
--
--1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
--
--Let us list the factors of the first seven triangle numbers:
--
-- 1: 1
-- 3: 1,3
-- 6: 1,2,3,6
--10: 1,2,5,10
--15: 1,3,5,15
--21: 1,3,7,21
--28: 1,2,4,7,14,28
--We can see that 28 is the first triangle number to have over five divisors.
--
--What is the value of the first triangle number to have over five hundred divisors?
--
module Prob12
    where
      import Data.List (group)

      factor n (p:ps) 
          | p*p > n        = [n]
          | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
          | otherwise      = factor n ps

      primes = 2 : filter ((==1) . length . primeFactors) [3,5..]
      primeFactors n = factor n primes
      triangleNumbers = scanl1 (+) [1..]
      answer = head (filter ((> 500) . numDivisors) triangleNumbers)
      numDivisors n = product (map (+1) (map (length) (group (primeFactors n))))

---

syntax highlighted by Code2HTML, v. 0.9.1