lib/primetable.c

   1 /*
   2  *      UCW Library -- Prime Number Table
   3  *
   4  *      (c) 2005 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 "lib/lib.h"
  11 #include "lib/binsearch.h"
  12
  13 /* A table of odd primes, each is about 1.2 times the previous one */
  14 static uns prime_table[] = {
  15   3,
  16   7,
  17   13,
  18   19,
  19   29,
  20   37,
  21   53,
  22   67,
  23   89,
  24   109,
  25   137,
  26   173,
  27   211,
  28   263,
  29   331,
  30   409,
  31   499,
  32   601,
  33   727,
  34   877,
  35   1061,
  36   1279,
  37   1543,
  38   1861,
  39   2239,
  40   2689,
  41   3229,
  42   3877,
  43   4657,
  44   5623,
  45   6761,
  46   8123,
  47   9767,
  48   11731,
  49   14083,
  50   16903,
  51   20287,
  52   24359,
  53   29243,
  54   35099,
  55   42131,
  56   50581,
  57   60703,
  58   72859,
  59   87433,
  60   104933,
  61   125927,
  62   151121,
  63   181361,
  64   217643,
  65   261223,
  66   313471,
  67   376171,
  68   451411,
  69   541699,
  70   650059,
  71   780119,
  72   936151,
  73   1123391,
  74   1348111,
  75   1617739,
  76   1941293,
  77   2329559,
  78   2795477,
  79   3354581,
  80   4025507,
  81   4830619,
  82   5796797,
  83   6956203,
  84   8347483,
  85   10017011,
  86   12020431,
  87   14424539,
  88   17309471,
  89   20771371,
  90   24925661,
  91   29910821,
  92   35892991,
  93   43071601,
  94   51685939,
  95   62023139,
  96   74427803,
  97   89313379,
  98   107176057,
  99   128611313,
 100   154333591,
 101   185200339,
 102   222240413,
 103   266688509,
 104   320026249,
 105   384031507,
 106   460837813,
 107   553005391,
 108   663606499,
 109   796327811,
 110   955593439,
 111   1146712139,
 112   1376054569,
 113   1651265507,
 114   1981518631,
 115   2377822387,
 116   2853386881,
 117   3424064269,
 118   4108877153,
 119   4294967291
 120 };
 121
 122 #define NPRIMES ARRAY_SIZE(prime_table)
 123
 124 uns
 125 next_table_prime(uns x)
 126 {
 127   if (x >= prime_table[NPRIMES-1])
 128     return 0;
 129   else
 130     return prime_table[BIN_SEARCH_FIRST_GE(prime_table, NPRIMES, x+1)];
 131 }
 132
 133 uns
 134 prev_table_prime(uns x)
 135 {
 136   int i = BIN_SEARCH_FIRST_GE(prime_table, NPRIMES, x);
 137   return i ? prime_table[i-1] : 0;
 138 }
 139
 140 #ifdef TEST
 141
 142 #include <stdio.h>
 143
 144 int main(void)
 145 {
 146 #if 0           /* Generate the table */
 147   uns x = 3, xx;
 148   do
 149     {
 150       printf("  %u,\n", x);
 151       xx = x;
 152       x = nextprime(1.2*x);
 153     }
 154   while (x > xx);
 155 #else
 156   for (int i=1; i<=100; i++)
 157     printf("%d\t%d\t%d\n", i, next_table_prime(i), prev_table_prime(i));
 158   for (uns i=0xfffffff0; i; i++)
 159     printf("%u\t%u\t%u\n", i, next_table_prime(i), prev_table_prime(i));
 160   return 0;
 161 #endif
 162 }
 163
 164 #endif