c_cpp/etc/calc/prime.h

   1 /*
   2  * prime - quickly determine if a small number is prime
   3  *
   4  * Copyright (C) 1999-2007  Landon Curt Noll
   5  *
   6  * Calc is open software; you can redistribute it and/or modify it under
   7  * the terms of the version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * Calc is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  13  * Public License for more details.
  14  *
  15  * A copy of version 2.1 of the GNU Lesser General Public License is
  16  * distributed with calc under the filename COPYING-LGPL.  You should have
  17  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  18  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  *
  20  * @(#) $Revision: 30.1 $
  21  * @(#) $Id: prime.h,v 30.1 2007/03/16 11:09:46 chongo Exp $
  22  * @(#) $Source: /usr/local/src/bin/calc/RCS/prime.h,v $
  23  *
  24  * Under source code control:   1994/06/04 03:26:15
  25  * File existed as early as:    1994
  26  *
  27  * chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  28  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  29  */
  30
  31
  32 #if !defined(__PRIME_H__)
  33 #define __PRIME_H__
  34
  35
  36 #if defined(CALC_SRC)   /* if we are building from the calc source tree */
  37 # include "qmath.h"
  38 # include "have_const.h"
  39 #else
  40 # include <calc/math.h>
  41 # include <calc/have_const.h>
  42 #endif
  43
  44
  45 #define MAX_MAP_PRIME ((FULL)65521)        /* (2^16-15) larest prime in prmap */
  46 #define MAX_MAP_VAL   ((FULL)65535)        /* (2^16-1)  larest bit in pr_map */
  47 #define MAX_SM_PRIME  ((FULL)0xfffffffb)   /* (2^32-5)  larest 32 bit prime */
  48 #define MAX_SM_VAL    ((FULL)0xffffffff)   /* (2^32-1)  larest 32 bit value */
  49
  50 #define MAP_POPCNT    6541                 /* number of odd primes in pr_map */
  51
  52 #define NXT_MAP_PRIME ((FULL)65537)        /* (2^16+1)  smallest prime > 2^16 */
  53
  54 #define PIX_32B       ((FULL)203280221)    /* pix(2^32-1) - max pix() value */
  55
  56 /*
  57  * product of primes that fit into a long
  58  */
  59 #if BASEB == 32
  60 #define MAX_PFACT_VAL 52        /* max x, for which pfact(x) is a long */
  61 #define NXT_PFACT_VAL 14        /* next prime for higher pfact values */
  62 #else
  63 #define MAX_PFACT_VAL 28        /* max x, for which pfact(x) is a long */
  64 #define NXT_PFACT_VAL 8         /* next prime for higher pfact values */
  65 #endif
  66
  67 /*
  68  * If n is odd and 1 <= n <= MAX_MAP_VAL, then:
  69  *
  70  *      pr_map_bit(n) != 0  ==>  n is prime
  71  *      pr_map_bit(n) == 0  ==>  n is NOT prime
  72  */
  73 #define pr_map_bit(n) (pr_map[(HALF)(n)>>4] & (1 << (((HALF)(n)>>1)&0x7)))
  74
  75 /*
  76  * Limits for piXb tables.  Do not test about this value using the
  77  * given table, even though the table has a higher sentinal value.
  78  */
  79 #define MAX_PI10B ((1024*256)-1)        /* largest pi10b value to test */
  80 #define MAX_PI18B ((FULL)(0xFFFFFFFF))  /* largest pi18b value to test */
  81
  82 /*
  83  * Prime related external arrays.
  84  */
  85 EXTERN CONST unsigned short prime[];
  86 EXTERN CONST unsigned char pr_map[];
  87 EXTERN CONST unsigned short pi10b[];
  88 EXTERN CONST unsigned short pi18b[];
  89 EXTERN NUMBER _nxtprime_;               /* 2^32+15 - smallest prime > 2^32 */
  90 EXTERN CONST ZVALUE _nxt_prime_;        /* 2^32+15 - smallest prime > 2^32 */
  91 EXTERN CONST ZVALUE _jmpmod2_;          /* JMPMOD*2 as a ZVALUE */
  92
  93
  94 #endif /* !__PRIME_H__ */