lib/prime.c

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