module Data.Numbers where
import Data.List
primes :: [Integer]
primes = 2:3:primes'
where
1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
primes' = p : filter isPrime candidates
divides n p = n `mod` p == 0
isPrime :: Integer -> Bool
isPrime n = all (not .(\p-> (n `mod` p) == 0)) $ takeWhile (\p -> p*p <= n) primes
primeFactors :: Integer -> [Integer]
primeFactors n = primeFactors' n n [] primes where
primeFactors' n m l (p:ps)
| p>n = l
| mo == 0 = primeFactors' n d (p:l) (p:ps)
| otherwise = primeFactors' n n l ps where
(d,mo) = divMod m p
numOfFactors :: Integer -> Int
numOfFactors n = product (map ((+1).length) (group (primeFactors n)))
factorSum :: Integer -> Integer
factorSum = product.(map (\p@(x:xs) -> (product p * x 1) `div` (x1))).(group.primeFactors)
factors :: Integer -> [Integer]
factors n = 1:factors' n [] [2..] where
factors' n l (m:ms)
| m*m==n= m:l
| m*m>n = l
| r == 0 = factors' n (d:m:l) ms
| otherwise = factors' n l ms where
(d,r) = divMod n m