This SRFI provides utilities related to prime numbers.

`primes`

Returns a fresh SRFI 127 lazy sequence of primes. It is useful when you need primes for a short period of time — if you don’t keep a reference to the returned sequence, it will be garbage collected after you’re done with the primes. (Note that the calculation of a prime number needs the sequence of primes from the beginning, so even if your code only keeps a reference into the middle of the sequence, the entire sequence will be stored — you have to release all references in order to allow the sequence to be garbage collected.)

On the other hand, each sequence returned by

`primes`

is computed individually, duplicating computation.The rule of thumb is: if you use primes repeatedly throughout the program, invoke

`primes`

and store its value in a global variable, and you’ll save computation. If you need primes just once, invoke`primes`

at the point they are needed and abandon the result, and you’ll save space.;; show 10 prime numbers from 100-th one. (lseq-take (lseq-drop (primes) 100) 10) ⇒ (547 557 563 569 571 577 587 593 599 601)

`small-prime?`

*n*For positive integers less than

`small-prime-bound`

, this procedure determines if`n is prime or not, quickly and deterministically. If``n`is greater than or equal to this bound, this procedure returns`#f`

.This can be used to quickly filter out known primes; it never returns

`#t`

on composite numbers, but it may return`#f`

on sufficiently large prime numbers). The Miller-Rabin test below can tell if the input is definitely composite, but it may return`#t`

on some composite numbers.

`small-prime-bound`

[Variable]For all positive integers below this value

`small-prime?`

can determine whether it is a prime or not.

`miller-rabin-prime?`

*n [ num-tests ]*Check if an exact integer

`n`is a prime number, using the probabilistic Miller-Rabin algorithm, where`n`must be greater than 1. If this procedure returns`#f`

,`n`is a composite number. If this procedure returns`#t`

,`n`is*likely*a prime, but there’s a small probability that it is a false positive.Note that if

`n`is smaller than`small-prime-bound`

, the algorithm is deterministic; if it returns`#t`

,`n`is certainly a prime.If

`n`is greater than or equal to`small-prime-bound`

, we use a probabilistic test. We choose a random base integer to perform the Miller-Rabin test up to`num-tests`(7 times by default). The probability of returning`#t`

for a composite number is at most`(expt 4 (- num-tests))`

.

`bpsw-prime?`

*n*Check if an exact integer

`n`is a prime number, using (the Baillie-PSW primality test). It is deterministic, and is known to return a definitive answer for all numbers less than 2^{64}. For larger integers this can return`#t`

on a composite number, although no such number has been found yet. This procedure never returns`#f`

on a prime number.This test is slower than Miller-Rabin but fast enough for casual use, so it is handy when you want a definitive answer below the above range.

`naive-factorize`

*n [ divisor-limit ]*Factorize a positive integer

`n`by trying to divide it into all primes up to`(sqrt n)`

. Returns a list of prime factors, smallest first.(naive-factorize 142857) ⇒ (3 3 3 11 13 37)

Although this is a pretty naive method, this works well as long as any of

`n`’s factors are not larger than about 10^{7}.(naive-factorize 3644357367494986671013)) ⇒ (10670053 10670053 32010157)

If

`n`includes any larger prime factors, the performance becomes abysmal.Alternatively, providing the

`divisor-limit`argument specifies the upper bound of the prime number to be tried. If it is given,`naive-factorize`

returns a factor`f`unchanged if it can’t be divided by any primes less than or equal to`divisor-limit`. So, the last element of the returned list may be a composite number. This is useful for excluding trivial factors before applying more sophisticated factorizing algorithms.(naive-factorize 825877877739 1000) ⇒ (3 43 6402154091) ;; whereas (naive-factorize 825877877739) ⇒ (3 43 4591 1394501)

The procedure also memoizes the results on smaller values of

`n`to make things faster.

`mc-factorize`

*n*Factorize a positive integer

`n`using the algorithm described in R. P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), 176-184.This one is capable of handling much larger factors than

`naive-factorize`

, somewhere around 10^{20}or so.Since this method is probabilistic, the execution time may vary on the same

`n`. But it will always return the definitive results as long as every prime factor of`n`is smaller than an implementation-specified limit. If`n`contains a prime factor greater than the limit, the procedure may loop forever.

`jacobi`

*a n*Calculates the Jacobi symbol

`(`

.`a`/`n`)

`totient`

*n*Euler’s totient function of the nonnegative integer

`n`.The current implementation relies on

`mc-factorize`

above, so it may take a very long time if`n`contains large prime factors.