Created
July 2, 2022 17:25
-
-
Save coder3112/1f68528fa7934783c6abe11c0551cf1c to your computer and use it in GitHub Desktop.
Prime Factorization in haskell to return a list of tuples giving the divisor as well as the power it is raised to.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| -- Example: | |
| -- > pf 120 | |
| -- [(2,3),(3,1),(5,1)] since 120 = 2^3 * 3^1 * 5^1 | |
| -- Thanks to leftaroundbot on stackoverflow for helping me out. | |
| -- Tells us how many times a number can be divided by another | |
| -- Eg: >dividerPower 120 5 | |
| -- 1 | |
| dividerPower :: Integer -> Integer -> Int | |
| dividerPower n d | |
| | n`rem`d == 0 = 1 + dividerPower (n`quot`d) d | |
| | otherwise = 0 | |
| -- Tells us the quotient and the number of times a number can be divided by another. | |
| -- Eg > dividePower 120 5 | |
| -- (24,1) since 120 = 24 * 5^1 | |
| dividePower :: Integer -> Integer -> (Integer, Int) | |
| dividePower n d | |
| | r == 0 = (nfin, p' + 1) | |
| | otherwise = (n, 0) | |
| where | |
| (n', r) = n `quotRem` d | |
| (nfin, p') = dividePower n' d | |
| -- Uses the above functions to give the prime factorization. | |
| pf :: Integer -> [(Integer, Int)] | |
| pf = go 2 | |
| where | |
| go d n | |
| | n>1 = (if p>0 then ((d, p):) else id) $ go (d+1) n' | |
| | otherwise = [] | |
| where (n', p) = dividePower n d |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment