module Factory.Math.Implementations.Primes.TrialDivision(
trialDivision
) 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
isIndivisibleBy :: Integral i
=> i
-> [i]
-> Bool
isIndivisibleBy :: i -> [i] -> Bool
isIndivisibleBy i
numerator = (i -> Bool) -> [i] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((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
numerator i -> i -> i
forall a. Integral a => a -> a -> a
`rem`)) ([i] -> Bool) -> ([i] -> [i]) -> [i] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i -> i
forall i. Integral i => i -> i
Math.PrimeFactorisation.maxBoundPrimeFactor i
numerator)
trialDivision :: Integral prime => Data.PrimeWheel.NPrimes -> [prime]
trialDivision :: NPrimes -> [prime]
trialDivision NPrimes
0 = [prime
2, prime
3] [prime] -> [prime] -> [prime]
forall a. [a] -> [a] -> [a]
++ (prime -> Bool) -> [prime] -> [prime]
forall a. (a -> Bool) -> [a] -> [a]
filter (prime -> [prime] -> Bool
forall i. Integral i => i -> [i] -> Bool
`isIndivisibleBy` NPrimes -> [prime]
forall prime. Integral prime => NPrimes -> [prime]
trialDivision NPrimes
0 ) [prime
5 ..]
trialDivision NPrimes
wheelSize = PrimeWheel prime -> [prime]
forall i. PrimeWheel i -> [i]
Data.PrimeWheel.getPrimeComponents PrimeWheel prime
primeWheel [prime] -> [prime] -> [prime]
forall a. [a] -> [a] -> [a]
++ [prime]
indivisible where
primeWheel :: PrimeWheel prime
primeWheel = NPrimes -> PrimeWheel prime
forall i. Integral i => NPrimes -> PrimeWheel i
Data.PrimeWheel.mkPrimeWheel NPrimes
wheelSize
candidates :: [prime]
candidates = ((prime, [prime]) -> prime) -> [(prime, [prime])] -> [prime]
forall a b. (a -> b) -> [a] -> [b]
map (prime, [prime]) -> prime
forall a b. (a, b) -> a
fst ([(prime, [prime])] -> [prime]) -> [(prime, [prime])] -> [prime]
forall a b. (a -> b) -> a -> b
$ PrimeWheel prime -> [(prime, [prime])]
forall i. Integral i => PrimeWheel i -> [Distance i]
Data.PrimeWheel.roll PrimeWheel prime
primeWheel
indivisible :: [prime]
indivisible = ([prime] -> [prime] -> [prime]) -> ([prime], [prime]) -> [prime]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [prime] -> [prime] -> [prime]
forall a. [a] -> [a] -> [a]
(++) (([prime], [prime]) -> [prime])
-> (([prime], [prime]) -> ([prime], [prime]))
-> ([prime], [prime])
-> [prime]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([prime] -> [prime]) -> ([prime], [prime]) -> ([prime], [prime])
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
Control.Arrow.second (
(prime -> Bool) -> [prime] -> [prime]
forall a. (a -> Bool) -> [a] -> [a]
filter (prime -> [prime] -> Bool
forall i. Integral i => i -> [i] -> Bool
`isIndivisibleBy` [prime]
indivisible )
) (([prime], [prime]) -> [prime]) -> ([prime], [prime]) -> [prime]
forall a b. (a -> b) -> a -> b
$ (prime -> Bool) -> [prime] -> ([prime], [prime])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (
prime -> prime -> Bool
forall a. Ord a => a -> a -> Bool
< prime -> prime
forall n. Num n => n -> n
Math.Power.square ([prime] -> prime
forall a. [a] -> a
head [prime]
candidates)
) [prime]
candidates