Implement prime number functions

[stylewarning]

Probably in a new package coalton-librar/math/primes.

Implement the following new prime number routines on Integral instances:

• (prime? x) which uses a deterministic primality test like AKS
• (miller-rabin-prime? n x) which does the Miller-Rabin test n times. Documentation should give a false-positive bound from n.
• (probable-prime? x) which uses Miller-Rabin for a suitable default n.
• (primes) which returns an iterator for all primes (perhaps using techniques from here).
• (coprime? a b) which checks coprimality of a and b
• (factorize n) which returns a sequence of prime factors of n

[shirok]

Do you have in mind a specific existing implementation? I've written some in Gauche and can port it.

https://github.com/shirok/Gauche/blob/master/lib/math/prime.scm

[stylewarning]

@shirok Nothing specific, except maybe the example Haskell sieve that seems relatively efficient.

[karlosz]

I frequently need a factorize-with-multiplicity type of routine which does prime factorization but lists the prime factors with their multiplicities (very useful for other number theoretic routines).

Both factorize and factorize-with-multiplicity can be supported with an underlying prime-factor routine that finds some prime factor of n. Many factorization routines in fact only return some not-necessarily-prime factor, most of the time non-deterministically.

Perhaps all of these should be exported, though if it's important to keep things deterministic then perhaps only factorize and factorize-with-multiplicity.

[shirok]

Gauche's library provides it (we call it grouped-factorize, which isn't a good name).

It has all features listed in the issue except coprime?, which can be trivially written with gcd.
https://practical-scheme.net/gauche/man/gauche-refe-draft/Prime-numbers.html