For more information including compatibility, examples and test cases, see https://github.com/petercrlane/r7rs-libs

SLIB Documentation: http://people.csail.mit.edu/jaffer/slib/Prime-Numbers.html#Prime-Numbers

0.1. Factor: (import (slib factor))

Functions for testing if numbers are primes, generating prime numbers, and to factor numbers.

These functions use the Solovay-Strassen primality test:

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

0.1.1. factor

factor takes one argument and returns a list of the prime factors of that number: the numbers are in no guaranteed order.

> (factor 5)
(5)
> (factor 100)
(5 5 2 2)

0.1.2. jacobi-symbol

The jacobi-symbol is used in modular arithmetic with one application, as here, being tests for primality. The function returns 0, -1 or 1 given two integers.

> (jacobi-symbol 15 7)
1
> (jacobi-symbol 63 7)
0
> (jacobi-symbol 7 15)
-1

0.1.3. prime:trials

prime:trials controls the likelihood that prime? will accept a composite number as a prime. The probability is 2^(- prime:trials)

prime:trials is a parameter object, so you can change it to a higher value, if required:

> (prime:trials)
30
> (prime:trials 100)
> (prime:trials)
100

0.1.4. prime?

prime? returns true or false depending on if the given number passes the Solovay-Strassen primality test.

> (prime? 17)
#t
> (prime? 1)
#f

0.1.5. primes<

primes< accepts two arguments: a start value and a count. It returns a list of count prime numbers less than the start value.

> (primes< 18 2)
(13 17)

0.1.6. primes>

primes> accepts two arguments: a start value and a count. It returns a list of count prime numbers greater than the start value.

> (primes> 18 2)
(19 23)