Safe Haskell | None |
---|---|

Language | Haskell98 |

A module for finding prime factors.

# Documentation

module Math.NumberTheory.Prime

pfactors :: Integer -> [Integer] Source

List the prime factors of n (with multiplicity). For example: >>> pfactors 60 [2,2,3,5]

This says that 60 = 2 * 2 * 3 * 5

The algorithm uses trial division to find small factors, followed if necessary by the elliptic curve method to find larger factors. The running time increases with the size of the second largest prime factor of n. It can find 10-digit prime factors in seconds, but can struggle with 20-digit prime factors.

ppfactors :: Integer -> [(Integer, Int)] Source

List the prime power factors of n. For example: >>> ppfactors 60 [(2,2),(3,1),(5,1)]

This says that 60 = 2^2 * 3^1 * 5^1

pfactorsTo :: Integer -> [(Integer, [Integer])] Source

Find the prime factors of all numbers up to n. Thus `pfactorsTo n`

is equivalent to `[(m, pfactors m) | m <- [1..n]]`

,
except that the results are not returned in order. For example:
>>> pfactorsTo 10
[(8,[2,2,2]),(4,[2,2]),(6,[3,2]),(10,[5,2]),(2,[2]),(9,[3,3]),(3,[3]),(5,[5]),(7,[7]),(1,[])]

`pfactorsTo n`

is significantly faster than `map pfactors [1..n]`

for larger n.

ppfactorsTo :: Integer -> [(Integer, [(Integer, Int)])] Source

Find the prime power factors of all numbers up to n. Thus `ppfactorsTo n`

is equivalent to `[(m, ppfactors m) | m <- [1..n]]`

,
except that the results are not returned in order. For example:
>>> ppfactorsTo 10
[(8,[(2,3)]),(4,[(2,2)]),(6,[(3,1),(2,1)]),(10,[(5,1),(2,1)]),(2,[(2,1)]),(9,[(3,2)]),(3,[(3,1)]),(5,[(5,1)]),(7,[(7,1)]),(1,[])]

`ppfactorsTo n`

is significantly faster than `map ppfactors [1..n]`

for larger n.