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
Requirements
Code reference
