Add primality testing and next_prime()/prev_prime()

2 files changed, 30 insertions, 0 deletions

diff --git a/builtins/integers.c b/builtins/integers.c
index 0bf7dc22..87d1f0ad 100644
--- a/builtins/integers.c
+++ b/builtins/integers.c
@@ -330,6 +330,33 @@ public Int_t Int$from_text(CORD text) {
     return Int$from_mpz(i);
 }
 
+public bool Int$is_prime(Int_t x, Int_t reps)
+{
+    mpz_t p;
+    mpz_init_set_int(p, x);
+    if (Int$compare(&reps, (Int_t[1]){I_small(9999)}, &$Int) > 0)
+        fail("Number of prime-test repetitions should not be above 9999");
+    int reps_int = Int_to_Int32(reps, false);
+    return (mpz_probab_prime_p(p, reps_int) != 0);
+}
+
+public Int_t Int$next_prime(Int_t x)
+{
+    mpz_t p;
+    mpz_init_set_int(p, x);
+    mpz_nextprime(p, p);
+    return Int$from_mpz(p);
+}
+
+public Int_t Int$prev_prime(Int_t x)
+{
+    mpz_t p;
+    mpz_init_set_int(p, x);
+    if (mpz_prevprime(p, p) == 0)
+        fail("There is no prime number before %r", Int$as_text(&x, false, &$Int));
+    return Int$from_mpz(p);
+}
+
 public const TypeInfo $Int = {
     .size=sizeof(Int_t),
     .align=__alignof__(Int_t),
diff --git a/builtins/integers.h b/builtins/integers.h
index edfd07dd..ed3e293c 100644
--- a/builtins/integers.h
+++ b/builtins/integers.h
@@ -117,6 +117,9 @@ Int_t Int$slow_bit_xor(Int_t x, Int_t y);
 Int_t Int$slow_negative(Int_t x);
 Int_t Int$slow_negated(Int_t x);
 Int_t Int$abs(Int_t x);
+bool Int$is_prime(Int_t x, Int_t reps);
+Int_t Int$next_prime(Int_t x);
+Int_t Int$prev_prime(Int_t x);
 
 extern const TypeInfo $Int;