{-
	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
	 )