{--
Prime numbers
Some Haskell exercises
Sebastian Krause 2020
- primes n
returns a list of prime numbers [2 .. n]
- primes1 n, primes2 n, primes3 n, primes4 n
return a list of prime numbers [2 .. n]
They are sorted by speed - prime1 is the fastest one and
is therefore linked to primes n
You may check out which one is the most beautiful one ;-)
- primetwins n
returns a list of prime twins [2 .. n]]
- isprime n
checks if the given number is a prime number
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
MA 02110-1301, USA.
--}
{--
Get a list of prime numbers now.
--}
-- 1) Fastest code here: Sieve of Erastothenes with given first values
primes1 :: Integer -> [Integer]
primes1 n
| n < 100 = filter (<= n) [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
| otherwise = foldr( \t l -> filter
(\z -> z <= t || (mod z t) > 0 )
l)
[2 .. n]
(primes1 (sqr n))
-- 2) Sieve of Erastothenes
primes2 :: Integer -> [Integer]
primes2 x = foldr( \t l -> filter
(\z -> z <= t || (mod z t) > 0 )
l)
[2 .. x]
[2 .. (sqr x) ]
-- 3) Compact version, checks only prime numbers known by now
-- as dividing candidates
primes3 :: Integer -> [Integer]
primes3 n = foldr( \z tl -> if (foldr (\t w -> w && (mod z t) > 0) True tl) then (tl ++ [z]) else tl) [2] (reverse [2 .. n])
-- 4) Mathematical version: The set of all x in [2, n] without divisor d < n
primes4 :: Integer ->[Integer]
primes4 n = [ z | z <- [2..n], all (\t -> mod z t > 0) [2..sqr z] ]
{--
Other stuff, based on primes1 (mostly)
--}
-- List of all prime twins [2 .. n]
primetwins :: Integer -> [(Integer, Integer)]
primetwins n = twinfilter (primes1 n)
-- Is n prime?
isprime :: Integer -> Bool
isprime n = n > 1 && foldr (\t w -> w && (mod n t) > 0) True (primes1 (sqr n))
-- Assistant functions
-- maps [p1, p2, p3] to [(p1,p2)] if p1, p2 are twins (and p3 not)
twinfilter :: [Integer] -> [(Integer, Integer)]
twinfilter x = case x of
[] -> []
(y:[]) -> []
(y:(z:zs)) -> if (z - y == 2) then [(y,z)] ++ (twinfilter (z:zs)) else (twinfilter (z:zs))
-- Only for computing the square root of n as Integer
max_int :: [Integer] -> Integer
max_int x = foldr (\a b -> if a < b then b else a) 0 x
sqr :: Integer -> Integer
sqr x = max_int [ z | z <- [0..x], z*z < x ]
-- Setting the fastest algorithmus as default
primes = primes1