GNU Info

(slib.info)Prime Numbers

---

Next: Random Numbers Prev: Modular Arithmetic Up: Mathematical Packages

---

Enter node , (file) or (file)node

Prime Numbers
=============

  `(require 'factor)'

 - Variable: prime:prngs
     PRIME:PRNGS is the random-state (Note: Random Numbers) used by
     these procedures.  If you call these procedures from more than one
     thread (or from interrupt), `random' may complain about reentrant
     calls.
  _Note:_ The prime test and generation procedures implement (or use)
the Solovay-Strassen primality test. See

   * Robert Solovay and Volker Strassen, `A Fast Monte-Carlo Test for
     Primality', SIAM Journal on Computing, 1977, pp 84-85.

 - Function: jacobi-symbol p q
     Returns the value (+1, -1, or 0) of the Jacobi-Symbol of exact
     non-negative integer P and exact positive odd integer Q.

 - Variable: prime:trials
     PRIME:TRIALS the maxinum number of iterations of Solovay-Strassen
     that will be done to test a number for primality.

 - Function: prime? n
     Returns `#f' if N is composite; `#t' if N is prime.  There is a
     slight chance `(expt 2 (- prime:trials))' that a composite will
     return `#t'.

 - Function: primes< start count
     Returns a list of the first COUNT prime numbers less than START.
     If there are fewer than COUNT prime numbers less than START, then
     the returned list will have fewer than START elements.

 - Function: primes> start count
     Returns a list of the first COUNT prime numbers greater than START.

 - Function: factor k
     Returns a list of the prime factors of K.  The order of the
     factors is unspecified.  In order to obtain a sorted list do
     `(sort! (factor K) <)'.