Permalink
Fetching contributors…
Cannot retrieve contributors at this time
61 lines (50 sloc) 1.6 KB
-- 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 System.IO.Console
import Class.Category
import Class.Show
import Data.Function
import Data.Numeric
import Data.Stream
import Data.Tuple
import Data.List
import Data.Text
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 -> 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 -> x < n)
$ primes 2
main ()
= forS (enumFromTo 1 5) $ λk
-> do write $ "k = " % show k % ": "
forS (listOfStream $ stake 10 $ kPrimes k) $ λx
-> write $ show x % " "
write "\n"