{- 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, conceptually infinite, list of /prime-numbers/, using /Trial Division/. -} module Factory.Math.Implementations.Primes.TrialDivision( -- * Functions trialDivision -- ** Predicates -- isIndivisibleBy ) where import qualified Control.Arrow import qualified Data.List import qualified Factory.Math.Power as Math.Power import qualified Factory.Math.PrimeFactorisation as Math.PrimeFactorisation import qualified Factory.Data.PrimeWheel as Data.PrimeWheel -- | Uses /Trial Division/, to determine whether the specified candidate is indivisible by all potential denominators from the specified list. isIndivisibleBy :: Integral i => i -- ^ The numerator. -> [i] -- ^ The denominators of which it must not be a multiple. -> Bool isIndivisibleBy numerator = all ((/= 0) . (numerator `mod`)) . takeWhile (<= Math.PrimeFactorisation.maxBoundPrimeFactor numerator) {-# INLINE isIndivisibleBy #-} {- | * For each candidate, confirm indivisibility, by all /primes/ smaller than its /square-root/. * The candidates to sieve, are generated by a 'Data.PrimeWheel.PrimeWheel', of parameterised, but static, size; <http://en.wikipedia.org/wiki/Wheel_factorization>. -} trialDivision :: Integral prime => Data.PrimeWheel.NPrimes -> [prime] trialDivision 0 = [2, 3] ++ filter (`isIndivisibleBy` trialDivision 0 {-recurse-}) [5 ..] --No faster than using 'Data.PrimeWheel.mkPrimeWheel 0', but apparently better space-complexity ?! trialDivision wheelSize = Data.PrimeWheel.getPrimeComponents primeWheel ++ indivisible where primeWheel = Data.PrimeWheel.mkPrimeWheel wheelSize candidates = map fst $ Data.PrimeWheel.roll primeWheel indivisible = uncurry (++) . Control.Arrow.second ( filter (`isIndivisibleBy` indivisible {-recurse-}) ) $ Data.List.span ( < Math.Power.square (head candidates) --The first composite candidate, is the square of the next prime after the wheel's constituent ones. ) candidates