Prime enumeration

Function

definition $p : {\mathbb N}_+\to{\mathbb P}$
definition $p(1):=2$
definition $p(n+1):={\mathrm{min}}({\mathbb P}\setminus{X_n})$
with $X_n\equiv\{m\in{\mathbb P}\mid m\le 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

Element of

Bijective function

Requirements

Prime number

Code reference

Least divisor function