-- Almost Prime -- https://rosettacode.org/wiki/Almost_prime -- -- A k-Almost-prime is a natural number 'n' that is the product of 'k' -- (possibly identical) primes. So, for example, 1-almost-primes, where -- k=1, are the prime numbers themselves; 2-almost-primes are the semiprimes. -- The task is to write a function/method/subroutine/... that generates -- k-almost primes and use it to create a table here of the first ten -- members of k-Almost primes for 1<=K<=5. -- module Main import Data.List import Data.Text import Data.Function import Data.Stream import System.IO.Console where -- | A stream of prime numbers. primes (c0: Nat): Stream Nat Nat = sfilter isPrime \$ senumFrom 2 -- | Check if a number is prime. -- Use Wilson's theorem to check for primality, being sure to take -- the mod of the running sum to avoid integer overflow. isPrime (n: Nat): Bool = foldl (λ(acc x: Nat) -> rem (x * acc) n) 1 (enumFromTo 1 (n - 1)) == (n - 1) -- | A stream of k-almost-prime numbers. kPrimes (k: Nat): Stream Nat Nat = sfilter (isKPrime k) (senumFrom 2) -- | Check if some number is k-almost-prime. isKPrime (k n: Nat): Bool | k == 1 = isPrime n | otherwise = sany \$ smap (isKPrime (k - 1)) \$ smap fst \$ sfilter (eq 0 ∘ snd) \$ smap (divMod n) \$ stakeWhile (λ(x: Nat) -> x < n) \$ primes 2 main () = forS (enumFromTo 1 5) (λ(k: Nat#) -> do write \$ "k = " % showNat k % ": " forS (listOfStream \$ stake 10 \$ kPrimes k) (λ(x: Nat#) -> write \$ showNat x % " ") write "\n")