ucw/prime.h

   1 /*
   2  *      The UCW Library -- Prime numbers
   3  *
   4  *      (c) 2008 Michal Vaner <vorner@ucw.cz>
   5  *
   6  *      Code taken from ucw/lib.h by:
   7  *
   8  *      (c) 1997--2008 Martin Mares <mj@ucw.cz>
   9  *      (c) 2005 Tomas Valla <tom@ucw.cz>
  10  *      (c) 2006 Robert Spalek <robert@ucw.cz>
  11  *      (c) 2007 Pavel Charvat <pchar@ucw.cz>
  12  *
  13  *      This software may be freely distributed and used according to the terms
  14  *      of the GNU Lesser General Public License.
  15  */
  16
  17 #ifndef _UCW_PRIME_H
  18 #define _UCW_PRIME_H
  19
  20 #include <ucw/lib.h>
  21
  22 #ifdef CONFIG_UCW_CLEAN_ABI
  23 #define isprime ucw_isprime
  24 #define next_table_prime ucw_next_table_prime
  25 #define nextprime ucw_nextprime
  26 #define prev_table_prime ucw_prev_table_prime
  27 #endif
  28
  29 /* prime.c */
  30
  31 /**
  32  * Return a non-zero value iff @x is a prime number.
  33  * The time complexity is `O(sqrt(x))`.
  34  **/
  35 int isprime(uint x);
  36
  37 /**
  38  * Return some prime greater than @x. The function does not checks overflows, but it should
  39  * be safe at least for @x lower than `1U << 31`.
  40  * If the Cramer's conjecture is true, it should have complexity `O(sqrt(x) * log(x)^2)`.
  41  **/
  42 uint nextprime(uint x);
  43
  44 /* primetable.c */
  45
  46 /**
  47  * Quickly lookup a precomputed table to return a prime number greater than @x.
  48  * Returns zero if there is no such prime (we guarantee the existance of at
  49  * least one prime greater than `1U << 31` in the table).
  50  **/
  51 uint next_table_prime(uint x);
  52
  53 /**
  54  * Quickly lookup a precomputed table to return a prime number smaller than @x.
  55  * Returns zero if @x is smaller than `7`.
  56  **/
  57 uint prev_table_prime(uint x);
  58
  59 #endif // _UCW_PRIME_H