Summary

###########################################################################

	File:     factors.icn

	Subject:  Procedures related to factors and prime numbers

	Authors:  Ralph E. Griswold and Gregg M. Townsend

	Date:     June 11, 2001

###########################################################################

   This file is in the public domain.

###########################################################################

  This file contains procedures related to factorization and prime
  numbers.

	divisors(n)	generates 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 i is square free

###########################################################################

  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.

###########################################################################

  Requires: Large-integer arithmetic; prime.lst for primel() and primorial().

###########################################################################

  Links:  io, numbers

###########################################################################

This file is part of the (main) package.

divisors(n)

: generate the divisors of n

factorial(n)

: return n! (n factorial)

factors(i, j)

: return list of factors

genfactors(i, j)

: generate prime factors of integer

gfactorial(n, i)

: generalized factorial

ispower(i, j)

: test for integer power

isprime(n)

: test for primality

nxtprime(n)

: next prime beyond n

pfactors(i)

: primes that divide integer

prdecomp(i)

: prime decomposition

prime()

: generate primes

primel()

: primes from list

primorial(i, j)

: product of primes

sfactors(i, j)

 return factors in string form

squarefree(n)

: test for square-free number