-- | This is an assortment of number theorectic functions. As of now it's not very large or fast, but that should improve over time.
module Data.Numbers 
(
    primes,
    isPrime,
    primeFactors,
    numOfFactors,
    factorSum,
    factors) where

import Data.List
import Data.Numbers.Primes


-- | Checks whether a number is prime    
isPrime :: Integer -> Bool
isPrime n      = all (not .(\p-> (n `mod` p) == 0)) $ takeWhile (\p -> p*p <= n) primes

-- | Returns the prime factors for a given number
primeFactors :: Integer -> [Integer]  
primeFactors n = primeFactors' n n [] primes where
    -- die Ausgangszahl, der quotient vom letzten mal, die liste der primfaktoren, primzahlen
    primeFactors' n m l (p:ps) 
        -- die nächste primzahl ist größer als wir? dann sind wir fertig
        | p>n = l
        -- wir sind teilbar durch p? p an die liste vorne dranhängen, quotient merken
        | mo == 0 = primeFactors' n d (p:l) (p:ps)
        -- nicht teilbar? mit der nächsten primzahl von vorne anfangen
        | otherwise = primeFactors' n n l ps where
            (d,mo) = divMod m p
            
-- | Returns the number of divisors of a number. Uses <http://mathschallenge.net/index.php?section=faq&ref=number/number_of_divisors>
numOfFactors :: Integer -> Int
numOfFactors n = product (map ((+1).length) (group (primeFactors n)))

-- | Returns the sum of the factors of a number
factorSum :: Integer -> Integer
factorSum = product.(map (\p@(x:xs) -> (product p * x -1) `div` (x-1))).(group.primeFactors)

-- | Returns the factors of a number
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