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 /* prime.c */
  23
  24 /**
  25  * Return a non-zero value iff @x is a prime number.
  26  * The time complexity is `O(sqrt(x))`.
  27  **/
  28 int isprime(uns x);
  29
  30 /**
  31  * Return some prime greater than @x. The function does not checks overflows, but it should
  32  * be safe at least for @x lower than `1U << 31`.
  33  * If the Cramer's conjecture is true, it should have complexity `O(sqrt(x) * log(x)^2)`.
  34  **/
  35 uns nextprime(uns x);
  36
  37 /* primetable.c */
  38
  39 /**
  40  * Quickly lookup a precomputed table to return a prime number greater than @x.
  41  * Returns zero if there is no such prime (we guarantee the existance of at
  42  * least one prime greater than `1U << 31` in the table).
  43  **/
  44 uns next_table_prime(uns x);
  45
  46 /**
  47  * Quickly lookup a precomputed table to return a prime number smaller than @x.
  48  * Returns zero if @x is smaller than `7`.
  49  **/
  50 uns prev_table_prime(uns x);
  51
  52 #endif // _UCW_PRIME_H