pgen/pfilt: Special cases for primality checking.

Don't consider 1, 0, or anything negative to be prime.  Also, add a test
for pgen_primep(), because it's probably useful.

diff --git a/pfilt.c b/pfilt.c
index 7f44569..e502404 100644 (file)
--- a/pfilt.c
+++ b/pfilt.c
@@ -59,7 +59,9 @@ static int smallenough(mp *m)
     max = mp_sqr(max, max);
     max->a->n--; /* Permanent allocation */
   }
-  if (MP_CMP(m, <, max))
+  if (MP_CMP(m, <=, MP_ONE))
+    rc = PGEN_FAIL;
+  else if (MP_CMP(m, <, max))
     rc = PGEN_DONE;
   return (rc);
 }
@@ -91,6 +93,7 @@ int pfilt_smallfactor(mp *m)
        rc = PGEN_DONE;
       else
        rc = PGEN_FAIL;
+      break;
     }
   }
 

diff --git a/pgen.c b/pgen.c
index 86e31c1..d989a4c 100644 (file)
--- a/pgen.c
+++ b/pgen.c
@@ -351,6 +351,31 @@ int pgen_primep(mp *p, grand *gr)
 
 #include <mLib/testrig.h>
 
+static int t_primep(dstr *v)
+{
+  mp *m = *(mp **)v[0].buf;
+  int e = *(int *)v[1].buf;
+  int r;
+  grand *rng;
+  int ok = 1;
+
+  rng = fibrand_create(0);
+  r = pgen_primep(m, rng);
+  GR_DESTROY(rng);
+  if (e != r) {
+    fputs("\n*** primep failed", stderr);
+    fputs("\nm = ", stderr); mp_writefile(m, stderr, 10);
+    fprintf(stderr, "\nexpected %d", e);
+    fprintf(stderr, "\nreported %d", r);
+    fputc('\n', stderr);
+    ok = 0;
+  }
+
+  mp_drop(m);
+  assert(mparena_count(MPARENA_GLOBAL) == 0);
+  return (ok);  
+}
+
 static int verify(dstr *v)
 {
   mp *m = *(mp **)v[0].buf;
@@ -382,6 +407,7 @@ static int verify(dstr *v)
 
 static test_chunk tests[] = {
   { "pgen", verify, { &type_mp, &type_mp, 0 } },
+  { "primep", t_primep, { &type_mp, &type_int, 0 } },
   { 0, 0, { 0 } }
 };
 

diff --git a/tests/pgen b/tests/pgen
index 2593287..de04dbf 100644 (file)
--- a/tests/pgen
+++ b/tests/pgen
@@ -15,3 +15,15 @@ pgen {
   40831929843180254171317254073271577309351168965431122042755102715326515941762786951037109689522493525769 40831929843180254171317254073271577309351168965431122042755102715326515941762786951037109689522493526197;
   166359567317705838255275971708060308423814413741683015010175247351623188739655446196925981468626681882384215574706593049022467680136399439302347043107836749816290369600677730213469006507173065402294688841278559283358390567733443050775707749725690534182003442070447739085348456478911335969765393755383551520173 166359567317705838255275971708060308423814413741683015010175247351623188739655446196925981468626681882384215574706593049022467680136399439302347043107836749816290369600677730213469006507173065402294688841278559283358390567733443050775707749725690534182003442070447739085348456478911335969765393755383551520257;
 }
+
+primep {
+  -5 0;
+  -1 0;
+  0 0;
+  1 0;
+  2 1;
+  3 1;
+  4 0;
+  40301809 1;
+  40301811 0;
+}