procedure divisors: generate the divisors of n procedure divisorl: return list of divisors of n procedure factorial: return n! (n factorial) procedure factors: return list of factors procedure genfactors: generate prime factors of integer procedure gfactorial: generalized factorial procedure pfactors: primes that divide integer procedure ispower: test for integer power procedure isprime: test for primality procedure nxtprime: next prime beyond n procedure prdecomp: prime decomposition procedure prime: generate primes procedure primel: primes from list procedure primorial: product of primes procedure sfactors: return factors in string form procedure squarefree: test for square-free number
link factors
January 23, 2002; Ralph E. Griswold and Gregg M. Townsend
Requires: Large-integer arithmetic; prime.lst for primel() and primorial().
This file is in the public domain.
This file contains procedures related to factorization and prime
numbers.
divisors(n) generates the divisors of n.
divisorl(n) returns a list of the divisors of n.
factorial(n) returns n!. It fails if n is less than 0.
factors(i, j) returns a list containing the prime factors of i
limited to maximum value j; default, no limit.
genfactors(i, j)
like factors(), except factors are generated as
they are found.
gfactorial(n, i)
generalized factorial; n x (n - i) x (n - 2i) x ...
ispower(i, j) succeeds and returns root if i is k^j
isprime(n) succeeds if n is a prime.
nxtprime(n) returns the next prime number beyond n.
pfactors(i) returns a list containing the primes that divide i.
prdecomp(i) returns a list of exponents for the prime
decomposition of i.
prime() generates the primes.
primel() generates the primes from a precompiled list.
primorial(i,j) product of primes j <= i; j defaults to 1.
sfactors(i, j) as factors(i, j), except output is in string form
with exponents for repeated factors
squarefree(i) succeeds if the factors of i are distinct
____________________________________________________________
Notes: Some of these procedures are not fast enough for extensive work.
Factoring is believed to be a hard problem. factors() should only be
used for small numbers.