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