lib/prime.c

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