Prime enumeration
Function
definition | p:N+→P |
definition | p(1):=2 |
definition | p(n+1):=min(P∖Xn) |
with | Xn≡{m∈P∣m≤p(n)} |
Code
primes0 :: [Integer] primes0 = filter prime0 [2..] prime0 :: Integer -> Bool prime0 n | n < 1 = error "not a positive integer" | n == 1 = False | otherwise = ld n == n
using Least divisor function:
divides :: Integral a => a -> a -> Bool divides d n = rem n d == 0 ld :: Integral a => a -> a ld n = ldf 2 n ldf :: Integral a => a -> a -> a ldf k n | divides k n = k | k^2 > n = n | otherwise = ldf (k+1) n
using Set of divisors function:
divides :: Integral a => a -> a -> Bool divides d n = rem n d == 0