{- Copyright (C) 2011 Dr. Alistair Ward 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 3 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, see <http://www.gnu.org/licenses/>. -} {- | [@AUTHOR@] Dr. Alistair Ward [@DESCRIPTION@] Generates the constant, conceptally infinite, list of /prime-numbers/, using /Turner's Sieve/; <http://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division>. -} module Factory.Math.Implementations.Primes.TurnersSieve( -- * Functions turnersSieve ) where import qualified Factory.Math.Power as Math.Power {- | * For each /prime/, the infinite list of candidates greater than its /square/, is filtered for indivisibility; <http://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division>. * CAVEAT: though one can easily add a 'Data.PrimeWheel.PrimeWheel', it proved counterproductive. -} turnersSieve :: Integral prime => [prime] turnersSieve :: [prime] turnersSieve = prime 2 prime -> [prime] -> [prime] forall a. a -> [a] -> [a] : [prime] -> [prime] forall i. Integral i => [i] -> [i] sieve [prime 3, prime 5 ..] where sieve :: Integral i => [i] -> [i] sieve :: [i] -> [i] sieve [] = [] sieve (i prime : [i] candidates) = i prime i -> [i] -> [i] forall a. a -> [a] -> [a] : [i] -> [i] forall i. Integral i => [i] -> [i] sieve ( (i -> Bool) -> [i] -> [i] forall a. (a -> Bool) -> [a] -> [a] filter ( \i candidate -> ((i -> Bool) -> Bool) -> [i -> Bool] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool any ((i -> Bool) -> i -> Bool forall a b. (a -> b) -> a -> b $ i candidate) [ (i -> i -> Bool forall a. Ord a => a -> a -> Bool < i -> i forall n. Num n => n -> n Math.Power.square i prime), -- Unconditionally admit any candidate smaller than the square of the last prime. (i -> i -> Bool forall a. Eq a => a -> a -> Bool /= i 0) (i -> Bool) -> (i -> i) -> i -> Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . (i -> i -> i forall a. Integral a => a -> a -> a `rem` i prime) -- Ensure indivisibility, of all subsequent candidates, by the last prime discovered. ] ) [i] candidates )