Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.ARITHMETIC.PRIMES

Compute primes and factorize numbers. License: AGPL3 Copyright Pascal J. Bourguignon 2003 - 2012 This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>

README:

FUNCTION

Public

COMPUTE-PRIMES-TO (N)

DO: Compute an Eratostene sieve to find all prime numbers up to N. RETURN: An array of prime numbers.

FACTORIZE (N &OPTIONAL (PRIMES NIL))

N: an INTEGER PRIMES: a VECTOR of prime factors sorted in increasing order. RETURN: a SEXP of the form: (* uncomensurate-factor [ prime | (EXPT prime exponent) ]… [ -1 ] )

STR-DECODE (NUM PRIMES)

RETURN: A string decoding the integer NUM factorized with the PRIMES.

STR-ENCODE (STR PRIMES)

RETURN: An integer encoding the string STR factorized with the PRIMES.

Private

FACTORIZE-VECTOR (N PRIMES)

N: an INTEGER PRIMES: a VECTOR of prime factors sorted in increasing order. RETURN: a VECTOR of length (1+ (LENGTH PRIMES)), with the uncommensurate factor in the slot 0, and the exponents of the primes in the following slots. (PRIMES could have a 1 in the first slot!)

MACRO

Private

WHILE (CONDITION &BODY BODY)

While loop.