Primes

Primes.dcl

definition module Primes

isPrime   :: Int -> Bool
isPrimeMR :: Int -> Bool

primes      :: [Int]
primeArray  :: Int -> {#Bool}
primeList   :: Int -> [Int]
rangePrimes :: Int Int -> [Int]

fact :: (Int -> [Int])
countFact :: (Int -> Int)
sumFact :: (Int -> Int)

Primes.icl

implementation module Primes
import StdEnv, StdLib, BigInt

isPrime :: Int -> Bool
isPrime n
    | n < 2 = False
    | n == 2 = True
    | n rem 2 == 0 = False
    | otherwise = f n [3,5..]
where
    f n [x:xs] | x * x <= n = n rem x <> 0 && f n xs
               | otherwise = True

isPrimeMR :: Int -> Bool
isPrimeMR num
    | num == 2 = True
    | num < 2 || isEven num = False
    | otherwise = (all id o map f) xs
where
    n = toBigInt num
    two = toBigInt 2
    xs = (takeWhile ((>) n) o map toBigInt) [2, 7, 61]
    t = (hd o dropWhile isEven o iterate (flip (/) two) o flip (-) one) n
    f a = (check o hd o dropWhile p o iterate g) (t,y) where
        y = powMod a t n
        g (t,y) = (t*two, (y*y) rem n)
        p (t,y) = t <> n-one && y <> one && y <> n-one
        check (t,y)
            | y <> n-one && isEven t = False
            | otherwise = True

::PrimeRecord = {prime :: Int, square :: Int}

primes :: [Int]
primes =: [prime \\ {prime} <- ps] where
    ps = [{prime = 2, square = 4} : [{prime = n, square= n*n} \\ n <- [3..] | isPrime n]]
    isPrime n = f ps where
        f [{prime,square}:xs] | square <= n = n rem prime <> 0 && f xs
                              | otherwise = True

primeArray :: Int -> {#Bool}
primeArray n
    # primeArray = {createArray (n+1) True & [0] = False, [1] = False}
    # primeArray = {primeArray & [x] = False \\ x <- [4,6..n]}
    = sieve (takeWhile (\x = x*x <= n) primes) primeArray
where
    sieve [] arr = arr
    sieve [x:xs] arr = sieve xs {arr & [x*p] = False \\ p <- [2..n/x]}

primeList :: Int -> [Int]
primeList n = [x \\ x <- [0..] & p <-: primeArray n | p]

rangePrimes :: Int Int -> [Int]
rangePrimes top end
    | top <= root = dropWhile ((>) top) ps ++ rangePrimes (root+1) end
    | otherwise = [top+x \\ x <- [0..] & p <-: arr top end | p]
where
    root = (entier o sqrt o toReal) end
    ps = takeWhile ((>=) root) primes
    arr :: Int Int -> {#Bool}
    arr top end 
        # arr = createArray arraySize True
        = sieve ps arr
    where
        arraySize = end - top
        sieve [] arr = arr
        sieve [p:ps] arr = sieve ps {arr & [i] = False \\ i <- [first,first+p..arraySize-1]} where
            first | top rem p == 0 = 0
                  | otherwise = p - (top rem p)

fact :: (Int -> [Int])
fact = f [2:[3,5..]] where
    f [x:xs] n
        | n <= 1       = []
        | x * x > n    = [n]
        | n rem x == 0 = [x:f [x:xs] (n/x)]
        | otherwise    = f xs n

countFact :: (Int -> Int)
countFact = prod o map (inc o length) o group o fact

sumFact :: (Int -> Int)
sumFact = prod o map f o group o fact where
    f xs = sum [1:[x^y \\ x <- xs & y <- [1..]]]