ucw/prime.c

   1 /*
   2  *      UCW Library -- Prime Number Tests
   3  *
   4  *      (c) 1997 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include <ucw/lib.h>
  11 #include <ucw/prime.h>
  12
  13 static int                              /* Sequential search */
  14 __isprime(uint x)                       /* We know x != 2 && x != 3 */
  15 {
  16   uint test = 5;
  17
  18   if (x == 5)
  19     return 1;
  20   for(;;)
  21     {
  22       if (!(x % test))
  23         return 0;
  24       if (x / test <= test)
  25         return 1;
  26       test += 2;                        /* 6k+1 */
  27       if (!(x % test))
  28         return 0;
  29       if (x / test <= test)
  30         return 1;
  31       test += 4;                        /* 6k-1 */
  32     }
  33 }
  34
  35 int
  36 isprime(uint x)
  37 {
  38   if (x < 5)
  39     return (x == 2 || x == 3);
  40   switch (x % 6)
  41     {
  42     case 1:
  43     case 5:
  44       return __isprime(x);
  45     default:
  46       return 0;
  47     }
  48 }
  49
  50 uint
  51 nextprime(uint x)                       /* Returns some prime greater than x */
  52 {
  53   x += 5 - (x % 6);                     /* x is 6k-1 */
  54   for(;;)
  55     {
  56       x += 2;                           /* 6k+1 */
  57       if (__isprime(x))
  58         return x;
  59       x += 4;                           /* 6k-1 */
  60       if (__isprime(x))
  61         return x;
  62     }
  63 }
  64
  65 #ifdef TEST
  66
  67 #include <stdio.h>
  68 #include <stdlib.h>
  69
  70 int
  71 main(int argc, char **argv)
  72 {
  73   uint k = atol(argv[1]);
  74   printf("%d is%s prime\n", k, isprime(k) ? "" : "n't");
  75   printf("Next prime is %d\n", nextprime(k));
  76   return 0;
  77 }
  78
  79 #endif