-- |
-- Module:      Math.NumberTheory.Primes
-- Copyright:   (c) 2016-2018 Andrew.Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE LambdaCase        #-}

{-# OPTIONS_GHC -fno-warn-orphans #-}

module Math.NumberTheory.Primes
    ( Prime
    , unPrime
    , toPrimeIntegral
    , nextPrime
    , precPrime
    , UniqueFactorisation(..)
    , factorBack
    , -- * Old interface
      primes
    ) where

import Data.Bits
import Data.Coerce
import Data.Maybe
import Data.Word
import Numeric.Natural

import Math.NumberTheory.Primes.Counting (nthPrime, primeCount)
import qualified Math.NumberTheory.Primes.Factorisation.Montgomery as F (factorise)
import qualified Math.NumberTheory.Primes.Testing.Probabilistic as T (isPrime)
import Math.NumberTheory.Primes.Sieve.Eratosthenes (primes, sieveRange, primeList, psieveFrom, primeSieve)
import Math.NumberTheory.Primes.Small
import Math.NumberTheory.Primes.Types
import Math.NumberTheory.Utils (toWheel30, fromWheel30)
import Math.NumberTheory.Utils.FromIntegral

-- | A class for unique factorisation domains.
class Num a => UniqueFactorisation a where
  -- | Factorise a number into a product of prime powers.
  -- Factorisation of 0 is an undefined behaviour. Otherwise
  -- following invariants hold:
  --
  -- > abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n)))
  -- > all ((> 0) . snd) (factorise n)
  --
  -- >>> factorise (1 :: Integer)
  -- []
  -- >>> factorise (-1 :: Integer)
  -- []
  -- >>> factorise (6 :: Integer)
  -- [(Prime 2,1),(Prime 3,1)]
  -- >>> factorise (-108 :: Integer)
  -- [(Prime 2,2),(Prime 3,3)]
  --
  -- This function is a replacement
  -- for 'Math.NumberTheory.Primes.Factorisation.factorise'.
  -- If you were looking for the latter, please import
  -- "Math.NumberTheory.Primes.Factorisation" instead of this module.
  --
  -- __Warning:__ there are no guarantees of any particular
  -- order of prime factors, do not expect them to be ascending. E. g.,
  --
  -- >>> factorise 10251562501
  -- [(Prime 101701,1),(Prime 100801,1)]
  factorise :: a -> [(Prime a, Word)]
  -- | Check whether an argument is prime.
  -- If it is then return an associated prime.
  --
  -- >>> isPrime (3 :: Integer)
  -- Just (Prime 3)
  -- >>> isPrime (4 :: Integer)
  -- Nothing
  -- >>> isPrime (-5 :: Integer)
  -- Just (Prime 5)
  --
  -- This function is a replacement
  -- for 'Math.NumberTheory.Primes.Testing.isPrime'.
  -- If you were looking for the latter, please import
  -- "Math.NumberTheory.Primes.Testing" instead of this module.
  isPrime   :: a -> Maybe (Prime a)

instance UniqueFactorisation Int where
  factorise :: Int -> [(Prime Int, Word)]
factorise = [(Int, Word)] -> [(Prime Int, Word)]
coerce ([(Int, Word)] -> [(Prime Int, Word)])
-> (Int -> [(Int, Word)]) -> Int -> [(Prime Int, Word)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [(Int, Word)]
forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Int -> Maybe (Prime Int)
isPrime Int
n = if Integer -> Bool
T.isPrime (Int -> Integer
forall a. Integral a => a -> Integer
toInteger Int
n) then Prime Int -> Maybe (Prime Int)
forall a. a -> Maybe a
Just (Int -> Prime Int
forall a. a -> Prime a
Prime (Int -> Prime Int) -> Int -> Prime Int
forall a b. (a -> b) -> a -> b
$ Int -> Int
forall a. Num a => a -> a
abs Int
n) else Maybe (Prime Int)
forall a. Maybe a
Nothing

instance UniqueFactorisation Word where
  factorise :: Word -> [(Prime Word, Word)]
factorise = [(Word, Word)] -> [(Prime Word, Word)]
coerce ([(Word, Word)] -> [(Prime Word, Word)])
-> (Word -> [(Word, Word)]) -> Word -> [(Prime Word, Word)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> [(Word, Word)]
forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Word -> Maybe (Prime Word)
isPrime Word
n = if Integer -> Bool
T.isPrime (Word -> Integer
forall a. Integral a => a -> Integer
toInteger Word
n) then Prime Word -> Maybe (Prime Word)
forall a. a -> Maybe a
Just (Word -> Prime Word
forall a. a -> Prime a
Prime Word
n) else Maybe (Prime Word)
forall a. Maybe a
Nothing

instance UniqueFactorisation Integer where
  factorise :: Integer -> [(Prime Integer, Word)]
factorise = [(Integer, Word)] -> [(Prime Integer, Word)]
coerce ([(Integer, Word)] -> [(Prime Integer, Word)])
-> (Integer -> [(Integer, Word)])
-> Integer
-> [(Prime Integer, Word)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> [(Integer, Word)]
forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Integer -> Maybe (Prime Integer)
isPrime Integer
n = if Integer -> Bool
T.isPrime Integer
n then Prime Integer -> Maybe (Prime Integer)
forall a. a -> Maybe a
Just (Integer -> Prime Integer
forall a. a -> Prime a
Prime (Integer -> Prime Integer) -> Integer -> Prime Integer
forall a b. (a -> b) -> a -> b
$ Integer -> Integer
forall a. Num a => a -> a
abs Integer
n) else Maybe (Prime Integer)
forall a. Maybe a
Nothing

instance UniqueFactorisation Natural where
  factorise :: Natural -> [(Prime Natural, Word)]
factorise = [(Natural, Word)] -> [(Prime Natural, Word)]
coerce ([(Natural, Word)] -> [(Prime Natural, Word)])
-> (Natural -> [(Natural, Word)])
-> Natural
-> [(Prime Natural, Word)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> [(Natural, Word)]
forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Natural -> Maybe (Prime Natural)
isPrime Natural
n = if Integer -> Bool
T.isPrime (Natural -> Integer
forall a. Integral a => a -> Integer
toInteger Natural
n) then Prime Natural -> Maybe (Prime Natural)
forall a. a -> Maybe a
Just (Natural -> Prime Natural
forall a. a -> Prime a
Prime Natural
n) else Maybe (Prime Natural)
forall a. Maybe a
Nothing

-- | Restore a number from its factorisation.
factorBack :: Num a => [(Prime a, Word)] -> a
factorBack :: [(Prime a, Word)] -> a
factorBack = [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([a] -> a) -> ([(Prime a, Word)] -> [a]) -> [(Prime a, Word)] -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Prime a, Word) -> a) -> [(Prime a, Word)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (\(Prime a
p, Word
k) -> Prime a -> a
forall a. Prime a -> a
unPrime Prime a
p a -> Word -> a
forall a b. (Num a, Integral b) => a -> b -> a
^ Word
k)

-- | Smallest prime, greater or equal to argument.
--
-- > nextPrime (-100) ==    2
-- > nextPrime  1000  == 1009
-- > nextPrime  1009  == 1009
nextPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a
nextPrime :: a -> Prime a
nextPrime a
n
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
2    = a -> Prime a
forall a. a -> Prime a
Prime a
2
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
3    = a -> Prime a
forall a. a -> Prime a
Prime a
3
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
5    = a -> Prime a
forall a. a -> Prime a
Prime a
5
  | Bool
otherwise = [Prime a] -> Prime a
forall a. [a] -> a
head ([Prime a] -> Prime a) -> [Prime a] -> Prime a
forall a b. (a -> b) -> a -> b
$ (a -> Maybe (Prime a)) -> [a] -> [Prime a]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe a -> Maybe (Prime a)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime ([a] -> [Prime a]) -> [a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$
                  (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
n) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map a -> a
forall a. (Num a, Bits a) => a -> a
fromWheel30 [a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
n ..]
                  -- dropWhile is important, because fromWheel30 (toWheel30 n) may appear to be < n.
                  -- E. g., fromWheel30 (toWheel30 94) == 97

-- | Largest prime, less or equal to argument. Undefined, when argument < 2.
--
-- > precPrime 100 == 97
-- > precPrime  97 == 97
precPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a
precPrime :: a -> Prime a
precPrime a
n
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
2     = [Char] -> Prime a
forall a. HasCallStack => [Char] -> a
error [Char]
"precPrime: tried to take `precPrime` of an argument less than 2"
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
3     = a -> Prime a
forall a. a -> Prime a
Prime a
2
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
5     = a -> Prime a
forall a. a -> Prime a
Prime a
3
  | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
7     = a -> Prime a
forall a. a -> Prime a
Prime a
5
  | Bool
otherwise = [Prime a] -> Prime a
forall a. [a] -> a
head ([Prime a] -> Prime a) -> [Prime a] -> Prime a
forall a b. (a -> b) -> a -> b
$ (a -> Maybe (Prime a)) -> [a] -> [Prime a]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe a -> Maybe (Prime a)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime ([a] -> [Prime a]) -> [a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$
                  (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
n) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map a -> a
forall a. (Num a, Bits a) => a -> a
fromWheel30 [a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
n, a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
n a -> a -> a
forall a. Num a => a -> a -> a
- a
1 ..]
                  -- dropWhile is important, because fromWheel30 (toWheel30 n) may appear to be > n.
                  -- E. g., fromWheel30 (toWheel30 100) == 101

-------------------------------------------------------------------------------
-- Prime sequences

data Algorithm = IsPrime | Sieve

chooseAlgorithm :: Integral a => a -> a -> Algorithm
chooseAlgorithm :: a -> a -> Algorithm
chooseAlgorithm a
from a
to
  | a
to a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sieveRange
  Bool -> Bool -> Bool
&& a
to a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
from a -> a -> a
forall a. Num a => a -> a -> a
+ Double -> a
forall a b. (RealFrac a, Integral b) => a -> b
truncate (Double -> Double
forall a. Floating a => a -> a
sqrt (a -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
from) :: Double)
  = Algorithm
IsPrime
  | a
to a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sieveRange
  Bool -> Bool -> Bool
&& a
to a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
from a -> a -> a
forall a. Num a => a -> a -> a
+ Double -> a
forall a b. (RealFrac a, Integral b) => a -> b
truncate (Double
0.036 Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double -> Double
forall a. Floating a => a -> a
sqrt (a -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
from) Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
40000 :: Double)
  = Algorithm
IsPrime
  | Bool
otherwise
  = Algorithm
Sieve

succGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a
succGeneric :: Prime a -> Prime a
succGeneric = \case
  Prime a
2 -> a -> Prime a
forall a. a -> Prime a
Prime a
3
  Prime a
3 -> a -> Prime a
forall a. a -> Prime a
Prime a
5
  Prime a
5 -> a -> Prime a
forall a. a -> Prime a
Prime a
7
  Prime a
p -> [Prime a] -> Prime a
forall a. [a] -> a
head ([Prime a] -> Prime a) -> [Prime a] -> Prime a
forall a b. (a -> b) -> a -> b
$ (a -> Maybe (Prime a)) -> [a] -> [Prime a]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a -> Maybe (Prime a)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime (a -> Maybe (Prime a)) -> (a -> a) -> a -> Maybe (Prime a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. (Num a, Bits a) => a -> a
fromWheel30) [a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p a -> a -> a
forall a. Num a => a -> a -> a
+ a
1 ..]

succGenericBounded
  :: (Bits a, Integral a, UniqueFactorisation a, Bounded a)
  => Prime a
  -> Prime a
succGenericBounded :: Prime a -> Prime a
succGenericBounded = \case
  Prime a
2 -> a -> Prime a
forall a. a -> Prime a
Prime a
3
  Prime a
3 -> a -> Prime a
forall a. a -> Prime a
Prime a
5
  Prime a
5 -> a -> Prime a
forall a. a -> Prime a
Prime a
7
  Prime a
p -> case (a -> Maybe (Prime a)) -> [a] -> [Prime a]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a -> Maybe (Prime a)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime (a -> Maybe (Prime a)) -> (a -> a) -> a -> Maybe (Prime a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. (Num a, Bits a) => a -> a
fromWheel30) [a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p a -> a -> a
forall a. Num a => a -> a -> a
+ a
1 .. a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
forall a. Bounded a => a
maxBound] of
    []    -> [Char] -> Prime a
forall a. HasCallStack => [Char] -> a
error [Char]
"Enum.succ{Prime}: tried to take `succ' near `maxBound'"
    Prime a
q : [Prime a]
_ -> Prime a
q

predGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a
predGeneric :: Prime a -> Prime a
predGeneric = \case
  Prime a
2 -> [Char] -> Prime a
forall a. HasCallStack => [Char] -> a
error [Char]
"Enum.pred{Prime}: tried to take `pred' of 2"
  Prime a
3 -> a -> Prime a
forall a. a -> Prime a
Prime a
2
  Prime a
5 -> a -> Prime a
forall a. a -> Prime a
Prime a
3
  Prime a
7 -> a -> Prime a
forall a. a -> Prime a
Prime a
5
  Prime a
p -> [Prime a] -> Prime a
forall a. [a] -> a
head ([Prime a] -> Prime a) -> [Prime a] -> Prime a
forall a b. (a -> b) -> a -> b
$ (a -> Maybe (Prime a)) -> [a] -> [Prime a]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a -> Maybe (Prime a)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime (a -> Maybe (Prime a)) -> (a -> a) -> a -> Maybe (Prime a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. (Num a, Bits a) => a -> a
fromWheel30) [a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p a -> a -> a
forall a. Num a => a -> a -> a
- a
1, a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p a -> a -> a
forall a. Num a => a -> a -> a
- a
2 ..]

-- 'dropWhile' is important, because 'psieveFrom' can actually contain primes less than p.
enumFromGeneric :: Integral a => Prime a -> [Prime a]
enumFromGeneric :: Prime a -> [Prime a]
enumFromGeneric p :: Prime a
p@(Prime a
p')
  = [Prime a] -> [Prime a]
coerce
  ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (Prime a -> Prime a -> Bool
forall a. Ord a => a -> a -> Bool
< Prime a
p)
  ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ [[Prime a]] -> [Prime a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat
  ([[Prime a]] -> [Prime a]) -> [[Prime a]] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ ([Prime a] -> Bool) -> [[Prime a]] -> [[Prime a]]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (Bool -> Bool
not (Bool -> Bool) -> ([Prime a] -> Bool) -> [Prime a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Prime a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null)
  ([[Prime a]] -> [[Prime a]]) -> [[Prime a]] -> [[Prime a]]
forall a b. (a -> b) -> a -> b
$ (PrimeSieve -> [Prime a]) -> [PrimeSieve] -> [[Prime a]]
forall a b. (a -> b) -> [a] -> [b]
map PrimeSieve -> [Prime a]
forall a. Integral a => PrimeSieve -> [Prime a]
primeList
  ([PrimeSieve] -> [[Prime a]]) -> [PrimeSieve] -> [[Prime a]]
forall a b. (a -> b) -> a -> b
$ Integer -> [PrimeSieve]
psieveFrom
  (Integer -> [PrimeSieve]) -> Integer -> [PrimeSieve]
forall a b. (a -> b) -> a -> b
$ a -> Integer
forall a. Integral a => a -> Integer
toInteger a
p'

smallPrimesLimit :: Integral a => a
smallPrimesLimit :: a
smallPrimesLimit = Word16 -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16
forall a. Bounded a => a
maxBound :: Word16)

enumFromToGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a -> [Prime a]
enumFromToGeneric :: Prime a -> Prime a -> [Prime a]
enumFromToGeneric p :: Prime a
p@(Prime a
p') q :: Prime a
q@(Prime a
q')
  | a
p' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
forall a. Integral a => a
smallPrimesLimit, a
q' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
forall a. Integral a => a
smallPrimesLimit
  = (Word16 -> Prime a) -> [Word16] -> [Prime a]
forall a b. (a -> b) -> [a] -> [b]
map (a -> Prime a
forall a. a -> Prime a
Prime (a -> Prime a) -> (Word16 -> a) -> Word16 -> Prime a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word16 -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral) ([Word16] -> [Prime a]) -> [Word16] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Word16 -> Word16 -> [Word16]
smallPrimesFromTo (a -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
p') (a -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
q')
  | a
p' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
forall a. Integral a => a
smallPrimesLimit
  = (Word16 -> Prime a) -> [Word16] -> [Prime a]
forall a b. (a -> b) -> [a] -> [b]
map (a -> Prime a
forall a. a -> Prime a
Prime (a -> Prime a) -> (Word16 -> a) -> Word16 -> Prime a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word16 -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral) (Word16 -> Word16 -> [Word16]
smallPrimesFromTo (a -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
p') Word16
forall a. Integral a => a
smallPrimesLimit)
  [Prime a] -> [Prime a] -> [Prime a]
forall a. [a] -> [a] -> [a]
++ Prime a -> Prime a -> [Prime a]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric' (a -> Prime a
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
nextPrime a
forall a. Integral a => a
smallPrimesLimit) Prime a
q
  | Bool
otherwise
  = Prime a -> Prime a -> [Prime a]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric' Prime a
p Prime a
q

enumFromToGeneric'
  :: (Bits a, Integral a, UniqueFactorisation a)
  => Prime a
  -> Prime a
  -> [Prime a]
enumFromToGeneric' :: Prime a -> Prime a -> [Prime a]
enumFromToGeneric' p :: Prime a
p@(Prime a
p') q :: Prime a
q@(Prime a
q') = (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (Prime a -> Prime a -> Bool
forall a. Ord a => a -> a -> Bool
<= Prime a
q) ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (Prime a -> Prime a -> Bool
forall a. Ord a => a -> a -> Bool
< Prime a
p) ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$
  case a -> a -> Algorithm
forall a. Integral a => a -> a -> Algorithm
chooseAlgorithm a
p' a
q' of
    Algorithm
IsPrime -> a -> Prime a
forall a. a -> Prime a
Prime a
2 Prime a -> [Prime a] -> [Prime a]
forall a. a -> [a] -> [a]
: a -> Prime a
forall a. a -> Prime a
Prime a
3 Prime a -> [Prime a] -> [Prime a]
forall a. a -> [a] -> [a]
: a -> Prime a
forall a. a -> Prime a
Prime a
5 Prime a -> [Prime a] -> [Prime a]
forall a. a -> [a] -> [a]
: (a -> Maybe (Prime a)) -> [a] -> [Prime a]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (a -> Maybe (Prime a)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime (a -> Maybe (Prime a)) -> (a -> a) -> a -> Maybe (Prime a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
forall a. (Num a, Bits a) => a -> a
fromWheel30) [a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p' .. a -> a
forall a. (Integral a, Bits a) => a -> a
toWheel30 a
q']
    Algorithm
Sieve   ->
      if a
q' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sieveRange
      then           PrimeSieve -> [Prime a]
forall a. Integral a => PrimeSieve -> [Prime a]
primeList (PrimeSieve -> [Prime a]) -> PrimeSieve -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Integer -> PrimeSieve
primeSieve (Integer -> PrimeSieve) -> Integer -> PrimeSieve
forall a b. (a -> b) -> a -> b
$ a -> Integer
forall a. Integral a => a -> Integer
toInteger a
q'
      else (PrimeSieve -> [Prime a]) -> [PrimeSieve] -> [Prime a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap PrimeSieve -> [Prime a]
forall a. Integral a => PrimeSieve -> [Prime a]
primeList ([PrimeSieve] -> [Prime a]) -> [PrimeSieve] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Integer -> [PrimeSieve]
psieveFrom (Integer -> [PrimeSieve]) -> Integer -> [PrimeSieve]
forall a b. (a -> b) -> a -> b
$ a -> Integer
forall a. Integral a => a -> Integer
toInteger a
p'

enumFromThenGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a -> [Prime a]
enumFromThenGeneric :: Prime a -> Prime a -> [Prime a]
enumFromThenGeneric p :: Prime a
p@(Prime a
p') (Prime a
q') = case a
p' a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` a
q' of
  Ordering
LT -> (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
r') -> (a
r' a -> a -> a
forall a. Num a => a -> a -> a
- a
p') a -> a -> a
forall a. Integral a => a -> a -> a
`rem` a
delta a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0) ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Prime a -> [Prime a]
forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric Prime a
p
    where
      delta :: a
delta = a
q' a -> a -> a
forall a. Num a => a -> a -> a
- a
p'
  Ordering
EQ -> Prime a -> [Prime a]
forall a. a -> [a]
repeat Prime a
p
  Ordering
GT -> (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
r') -> (a
p' a -> a -> a
forall a. Num a => a -> a -> a
- a
r') a -> a -> a
forall a. Integral a => a -> a -> a
`rem` a
delta a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0) ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ [Prime a] -> [Prime a]
forall a. [a] -> [a]
reverse ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Prime a -> Prime a -> [Prime a]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric (a -> Prime a
forall a. a -> Prime a
Prime a
2) Prime a
p
    where
      delta :: a
delta = a
p' a -> a -> a
forall a. Num a => a -> a -> a
- a
q'

enumFromThenToGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric :: Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric p :: Prime a
p@(Prime a
p') (Prime a
q') r :: Prime a
r@(Prime a
r') = case a
p' a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` a
q' of
  Ordering
LT -> (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
t') -> (a
t' a -> a -> a
forall a. Num a => a -> a -> a
- a
p') a -> a -> a
forall a. Integral a => a -> a -> a
`rem` a
delta a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0) ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Prime a -> Prime a -> [Prime a]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric Prime a
p Prime a
r
    where
      delta :: a
delta = a
q' a -> a -> a
forall a. Num a => a -> a -> a
- a
p'
  Ordering
EQ -> if a
p' a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
r' then Prime a -> [Prime a]
forall a. a -> [a]
repeat Prime a
p else []
  Ordering
GT -> (Prime a -> Bool) -> [Prime a] -> [Prime a]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
t') -> (a
p' a -> a -> a
forall a. Num a => a -> a -> a
- a
t') a -> a -> a
forall a. Integral a => a -> a -> a
`rem` a
delta a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
0) ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ [Prime a] -> [Prime a]
forall a. [a] -> [a]
reverse ([Prime a] -> [Prime a]) -> [Prime a] -> [Prime a]
forall a b. (a -> b) -> a -> b
$ Prime a -> Prime a -> [Prime a]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric Prime a
r Prime a
p
    where
      delta :: a
delta = a
p' a -> a -> a
forall a. Num a => a -> a -> a
- a
q'

instance Enum (Prime Integer) where
  toEnum :: Int -> Prime Integer
toEnum = Int -> Prime Integer
nthPrime
  fromEnum :: Prime Integer -> Int
fromEnum = Integer -> Int
integerToInt (Integer -> Int)
-> (Prime Integer -> Integer) -> Prime Integer -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount (Integer -> Integer)
-> (Prime Integer -> Integer) -> Prime Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Prime Integer -> Integer
forall a. Prime a -> a
unPrime
  succ :: Prime Integer -> Prime Integer
succ = Prime Integer -> Prime Integer
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
succGeneric
  pred :: Prime Integer -> Prime Integer
pred = Prime Integer -> Prime Integer
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Integer -> [Prime Integer]
enumFrom = Prime Integer -> [Prime Integer]
forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Integer -> Prime Integer -> [Prime Integer]
enumFromTo = Prime Integer -> Prime Integer -> [Prime Integer]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Integer -> Prime Integer -> [Prime Integer]
enumFromThen = Prime Integer -> Prime Integer -> [Prime Integer]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Integer -> Prime Integer -> Prime Integer -> [Prime Integer]
enumFromThenTo = Prime Integer -> Prime Integer -> Prime Integer -> [Prime Integer]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Enum (Prime Natural) where
  toEnum :: Int -> Prime Natural
toEnum = Natural -> Prime Natural
forall a. a -> Prime a
Prime (Natural -> Prime Natural)
-> (Int -> Natural) -> Int -> Prime Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Natural
integerToNatural (Integer -> Natural) -> (Int -> Integer) -> Int -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Prime Integer -> Integer
forall a. Prime a -> a
unPrime (Prime Integer -> Integer)
-> (Int -> Prime Integer) -> Int -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Prime Integer
nthPrime
  fromEnum :: Prime Natural -> Int
fromEnum = Integer -> Int
integerToInt (Integer -> Int)
-> (Prime Natural -> Integer) -> Prime Natural -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount (Integer -> Integer)
-> (Prime Natural -> Integer) -> Prime Natural -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
naturalToInteger (Natural -> Integer)
-> (Prime Natural -> Natural) -> Prime Natural -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Prime Natural -> Natural
forall a. Prime a -> a
unPrime
  succ :: Prime Natural -> Prime Natural
succ = Prime Natural -> Prime Natural
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
succGeneric
  pred :: Prime Natural -> Prime Natural
pred = Prime Natural -> Prime Natural
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Natural -> [Prime Natural]
enumFrom = Prime Natural -> [Prime Natural]
forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Natural -> Prime Natural -> [Prime Natural]
enumFromTo = Prime Natural -> Prime Natural -> [Prime Natural]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Natural -> Prime Natural -> [Prime Natural]
enumFromThen = Prime Natural -> Prime Natural -> [Prime Natural]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Natural -> Prime Natural -> Prime Natural -> [Prime Natural]
enumFromThenTo = Prime Natural -> Prime Natural -> Prime Natural -> [Prime Natural]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Enum (Prime Int) where
  toEnum :: Int -> Prime Int
toEnum Int
n = if Integer
p Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Int -> Integer
intToInteger Int
forall a. Bounded a => a
maxBound
    then [Char] -> Prime Int
forall a. HasCallStack => [Char] -> a
error ([Char] -> Prime Int) -> [Char] -> Prime Int
forall a b. (a -> b) -> a -> b
$ [Char]
"Enum.toEnum{Prime}: " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
n [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"th prime = " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Integer -> [Char]
forall a. Show a => a -> [Char]
show Integer
p [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
" is out of bounds of Int"
    else Int -> Prime Int
forall a. a -> Prime a
Prime (Integer -> Int
integerToInt Integer
p)
    where
      Prime Integer
p = Int -> Prime Integer
nthPrime Int
n
  fromEnum :: Prime Int -> Int
fromEnum = Integer -> Int
integerToInt (Integer -> Int) -> (Prime Int -> Integer) -> Prime Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount (Integer -> Integer)
-> (Prime Int -> Integer) -> Prime Int -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Integer
intToInteger (Int -> Integer) -> (Prime Int -> Int) -> Prime Int -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Prime Int -> Int
forall a. Prime a -> a
unPrime
  succ :: Prime Int -> Prime Int
succ = Prime Int -> Prime Int
forall a.
(Bits a, Integral a, UniqueFactorisation a, Bounded a) =>
Prime a -> Prime a
succGenericBounded
  pred :: Prime Int -> Prime Int
pred = Prime Int -> Prime Int
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Int -> [Prime Int]
enumFrom = Prime Int -> [Prime Int]
forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Int -> Prime Int -> [Prime Int]
enumFromTo = Prime Int -> Prime Int -> [Prime Int]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Int -> Prime Int -> [Prime Int]
enumFromThen = Prime Int -> Prime Int -> [Prime Int]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Int -> Prime Int -> Prime Int -> [Prime Int]
enumFromThenTo = Prime Int -> Prime Int -> Prime Int -> [Prime Int]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Bounded (Prime Int) where
  minBound :: Prime Int
minBound = Int -> Prime Int
forall a. a -> Prime a
Prime Int
2
  maxBound :: Prime Int
maxBound = Int -> Prime Int
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
precPrime Int
forall a. Bounded a => a
maxBound

instance Enum (Prime Word) where
  toEnum :: Int -> Prime Word
toEnum Int
n = if Integer
p Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Word -> Integer
wordToInteger Word
forall a. Bounded a => a
maxBound
    then [Char] -> Prime Word
forall a. HasCallStack => [Char] -> a
error ([Char] -> Prime Word) -> [Char] -> Prime Word
forall a b. (a -> b) -> a -> b
$ [Char]
"Enum.toEnum{Prime}: " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
n [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"th prime = " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Integer -> [Char]
forall a. Show a => a -> [Char]
show Integer
p [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
" is out of bounds of Word"
    else Word -> Prime Word
forall a. a -> Prime a
Prime (Integer -> Word
integerToWord Integer
p)
    where
      Prime Integer
p = Int -> Prime Integer
nthPrime Int
n
  fromEnum :: Prime Word -> Int
fromEnum = Integer -> Int
integerToInt (Integer -> Int) -> (Prime Word -> Integer) -> Prime Word -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount (Integer -> Integer)
-> (Prime Word -> Integer) -> Prime Word -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> Integer
wordToInteger (Word -> Integer) -> (Prime Word -> Word) -> Prime Word -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Prime Word -> Word
forall a. Prime a -> a
unPrime
  succ :: Prime Word -> Prime Word
succ = Prime Word -> Prime Word
forall a.
(Bits a, Integral a, UniqueFactorisation a, Bounded a) =>
Prime a -> Prime a
succGenericBounded
  pred :: Prime Word -> Prime Word
pred = Prime Word -> Prime Word
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Word -> [Prime Word]
enumFrom = Prime Word -> [Prime Word]
forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Word -> Prime Word -> [Prime Word]
enumFromTo = Prime Word -> Prime Word -> [Prime Word]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Word -> Prime Word -> [Prime Word]
enumFromThen = Prime Word -> Prime Word -> [Prime Word]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Word -> Prime Word -> Prime Word -> [Prime Word]
enumFromThenTo = Prime Word -> Prime Word -> Prime Word -> [Prime Word]
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Bounded (Prime Word) where
  minBound :: Prime Word
minBound = Word -> Prime Word
forall a. a -> Prime a
Prime Word
2
  maxBound :: Prime Word
maxBound = Word -> Prime Word
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
precPrime Word
forall a. Bounded a => a
maxBound