{-# LANGUAGE BangPatterns #-}
module Math.NumberTheory.Primes.Factorisation.TrialDivision
( trialDivisionWith
, trialDivisionTo
, trialDivisionPrimeTo
) where
import Math.NumberTheory.Primes.Sieve.Eratosthenes (primeList, primeSieve, psieveList)
import Math.NumberTheory.Roots
import Math.NumberTheory.Primes.Types
import Math.NumberTheory.Utils
trialDivisionWith :: [Integer] -> Integer -> [(Integer, Word)]
trialDivisionWith :: [Integer] -> Integer -> [(Integer, Word)]
trialDivisionWith [Integer]
prs Integer
n
| Integer
n forall a. Ord a => a -> a -> Bool
< Integer
0 = [Integer] -> Integer -> [(Integer, Word)]
trialDivisionWith [Integer]
prs (-Integer
n)
| Integer
n forall a. Eq a => a -> a -> Bool
== Integer
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"trialDivision of 0"
| Integer
n forall a. Eq a => a -> a -> Bool
== Integer
1 = []
| Bool
otherwise = forall {a}.
(GcdDomain a, Integral a) =>
a -> a -> [a] -> [(a, Word)]
go Integer
n (forall a. Integral a => a -> a
integerSquareRoot Integer
n) [Integer]
prs
where
go :: a -> a -> [a] -> [(a, Word)]
go !a
m !a
r (a
p:[a]
ps)
| a
r forall a. Ord a => a -> a -> Bool
< a
p = [(a
m,Word
1)]
| Bool
otherwise =
case forall a. (Eq a, GcdDomain a) => a -> a -> (Word, a)
splitOff a
p a
m of
(Word
0,a
_) -> a -> a -> [a] -> [(a, Word)]
go a
m a
r [a]
ps
(Word
k,a
q) -> (a
p,Word
k) forall a. a -> [a] -> [a]
: if a
q forall a. Eq a => a -> a -> Bool
== a
1
then []
else a -> a -> [a] -> [(a, Word)]
go a
q (forall a. Integral a => a -> a
integerSquareRoot a
q) [a]
ps
go a
m a
_ [a]
_ = [(a
m,Word
1)]
trialDivisionTo :: Integer -> Integer -> [(Integer, Word)]
trialDivisionTo :: Integer -> Integer -> [(Integer, Word)]
trialDivisionTo Integer
bd
| Integer
bd forall a. Ord a => a -> a -> Bool
< Integer
100 = Integer -> Integer -> [(Integer, Word)]
trialDivisionTo Integer
100
| Integer
bd forall a. Ord a => a -> a -> Bool
< Integer
10000000 = [Integer] -> Integer -> [(Integer, Word)]
trialDivisionWith (forall a b. (a -> b) -> [a] -> [b]
map forall a. Prime a -> a
unPrime forall a b. (a -> b) -> a -> b
$ forall a. Integral a => PrimeSieve -> [Prime a]
primeList forall a b. (a -> b) -> a -> b
$ Integer -> PrimeSieve
primeSieve Integer
bd)
| Bool
otherwise = [Integer] -> Integer -> [(Integer, Word)]
trialDivisionWith (forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
<= Integer
bd) forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall a. Prime a -> a
unPrime forall a b. (a -> b) -> a -> b
$ [PrimeSieve]
psieveList forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. Integral a => PrimeSieve -> [Prime a]
primeList)
trialDivisionPrimeWith :: [Integer] -> Integer -> Bool
trialDivisionPrimeWith :: [Integer] -> Integer -> Bool
trialDivisionPrimeWith [Integer]
prs Integer
n
| Integer
n forall a. Ord a => a -> a -> Bool
< Integer
0 = [Integer] -> Integer -> Bool
trialDivisionPrimeWith [Integer]
prs (-Integer
n)
| Integer
n forall a. Ord a => a -> a -> Bool
< Integer
2 = Bool
False
| Bool
otherwise = forall {t}. Integral t => t -> t -> [t] -> Bool
go Integer
n (forall a. Integral a => a -> a
integerSquareRoot Integer
n) [Integer]
prs
where
go :: t -> t -> [t] -> Bool
go !t
m !t
r (t
p:[t]
ps) = t
r forall a. Ord a => a -> a -> Bool
< t
p Bool -> Bool -> Bool
|| t
m forall a. Integral a => a -> a -> a
`rem` t
p forall a. Eq a => a -> a -> Bool
/= t
0 Bool -> Bool -> Bool
&& t -> t -> [t] -> Bool
go t
m t
r [t]
ps
go t
_ t
_ [t]
_ = Bool
True
trialDivisionPrimeTo :: Integer -> Integer -> Bool
trialDivisionPrimeTo :: Integer -> Integer -> Bool
trialDivisionPrimeTo Integer
bd
| Integer
bd forall a. Ord a => a -> a -> Bool
< Integer
100 = Integer -> Integer -> Bool
trialDivisionPrimeTo Integer
100
| Integer
bd forall a. Ord a => a -> a -> Bool
< Integer
10000000 = [Integer] -> Integer -> Bool
trialDivisionPrimeWith (forall a b. (a -> b) -> [a] -> [b]
map forall a. Prime a -> a
unPrime forall a b. (a -> b) -> a -> b
$ forall a. Integral a => PrimeSieve -> [Prime a]
primeList forall a b. (a -> b) -> a -> b
$ Integer -> PrimeSieve
primeSieve Integer
bd)
| Bool
otherwise = [Integer] -> Integer -> Bool
trialDivisionPrimeWith (forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
<= Integer
bd) forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall a. Prime a -> a
unPrime forall a b. (a -> b) -> a -> b
$ [PrimeSieve]
psieveList forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. Integral a => PrimeSieve -> [Prime a]
primeList)