module Autolib.Util.Faktor 

( zerlege 
, primfaktoren
)


where


-- | in Primzahlpotenzen
type Zerlegung = [(Integer, Int)]


zerlege :: Integer -> Zerlegung
zerlege :: Integer -> Zerlegung
zerlege Integer
n | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = [Char] -> Zerlegung
forall a. HasCallStack => [Char] -> a
error [Char]
"Util.Zerlegung.zerlege"
zerlege Integer
n = ((Integer, Int) -> Bool) -> Zerlegung -> Zerlegung
forall a. (a -> Bool) -> [a] -> [a]
filter ( \ (Integer
p,Int
e) -> Int
e Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 ) 
	  (Zerlegung -> Zerlegung) -> Zerlegung -> Zerlegung
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Zerlegung
forall {t}. Integral t => t -> t -> [(t, Int)]
helper Integer
2 Integer
n 

helper :: t -> t -> [(t, Int)]
helper t
p t
1 = []
helper t
p t
n |  t
pt -> t -> t
forall a. Num a => a -> a -> a
*t
p t -> t -> Bool
forall a. Ord a => a -> a -> Bool
> t
n  = [ (t
n,Int
1) ]
helper t
p t
n = 
    let nrs :: [(t, t)]
nrs = ((t, t) -> (t, t)) -> (t, t) -> [(t, t)]
forall a. (a -> a) -> a -> [a]
iterate ( \ (t
n, t
r) -> t -> t -> (t, t)
forall a. Integral a => a -> a -> (a, a)
divMod t
n t
p ) ( t
n, t
0 )
	pre :: [(t, t)]
pre = ((t, t) -> Bool) -> [(t, t)] -> [(t, t)]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile ( \ (t
n,t
r) -> t
r t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 ) [(t, t)]
nrs 
	(t
m, t
s) = [(t, t)] -> (t, t)
forall a. HasCallStack => [a] -> a
last [(t, t)]
pre
	d :: t
d = if t
p t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
2 then t
1 
	    else if t
1 t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
p t -> t -> t
forall a. Integral a => a -> a -> a
`mod` t
6 then t
4
	    else t
2
    in ( t
p, [(t, t)] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(t, t)]
pre Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 ) (t, Int) -> [(t, Int)] -> [(t, Int)]
forall a. a -> [a] -> [a]
: t -> t -> [(t, Int)]
helper (t
pt -> t -> t
forall a. Num a => a -> a -> a
+t
d) t
m

primfaktoren :: Integer -> [ Integer ]
primfaktoren :: Integer -> [Integer]
primfaktoren = ((Integer, Int) -> Integer) -> Zerlegung -> [Integer]
forall a b. (a -> b) -> [a] -> [b]
map (Integer, Int) -> Integer
forall a b. (a, b) -> a
fst (Zerlegung -> [Integer])
-> (Integer -> Zerlegung) -> Integer -> [Integer]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Zerlegung
zerlege