5.5 Prime Numbers

(require 'factor)

Variable: prime:prngs ¶

prime:prngs is the random-state (see 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) <).