{-
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 .
-}
{- |
[@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 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 `rem`)) . takeWhile (<= Math.PrimeFactorisation.maxBoundPrimeFactor numerator)
{- |
* 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; .
-}
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-})
) $ span (
< Math.Power.square (head candidates) -- The first composite candidate, is the square of the next prime after the wheel's constituent ones.
) candidates