prime.c

Calc Software Package for Number Calc

/*
 * prime - quickly determine if a small number is prime
 *
 * Copyright (C) 1999  Landon Curt Noll
 *
 * Calc is open software; you can redistribute it and/or modify it under
 * the terms of the version 2.1 of the GNU Lesser General Public License
 * as published by the Free Software Foundation.
 *
 * Calc is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
 * Public License for more details.
 *
 * A copy of version 2.1 of the GNU Lesser General Public License is
 * distributed with calc under the filename COPYING-LGPL.  You should have
 * received a copy with calc; if not, write to Free Software Foundation, Inc.
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * @(#) $Revision: 29.2 $
 * @(#) $Id: prime.c,v 29.2 2000/06/07 14:02:13 chongo Exp $
 * @(#) $Source: /usr/local/src/cmd/calc/RCS/prime.c,v $
 *
 * Under source code control:	1994/06/04 03:26:14
 * File existed as early as:	1994
 *
 * chongo <was here> /\oo/\	http://www.isthe.com/chongo/
 * Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/
 */


#include "qmath.h"
#include "prime.h"
#include "jump.h"
#include "have_const.h"


/*
 * odd prime bitmap for odd values < 2^16
 *
 * pr_map[i] & (1<<j) == 1  ==>	 i*16 + j*2 + 1 is prime
 *			 0  ==>	 i*16 + j*2 + 1 is not prime
 *
 * This table is useful to quickly determine if a 16 bit odd number
 * is prime.  Use the prime[] array to quickly walk thru the 16 bit
 * off primes.
 */
CONST unsigned char pr_map[(MAX_MAP_VAL/8)+1] = {
    110,203,180,100,154, 18,109,129, 50, 76, 74,134, 13,130,150, 33,
    201, 52,  4, 90, 32, 97,137,164, 68, 17,134, 41,209,130, 40, 74,
     48, 64, 66, 50, 33,153, 52,  8, 75,  6, 37, 66,132, 72,138, 20,
      5, 66, 48,108,  8,180, 64, 11,160,  8, 81, 18, 40,137,  4,101,
    152, 48, 76,128,150, 68, 18,128, 33, 66, 18, 65,201,  4, 33,192,
     50, 45,152,  0,  0, 73,  4,  8,129,150,104,130,176, 37,  8, 34,
     72,137,162, 64, 89, 38,  4,144,  6, 64, 67, 48, 68,146,  0,105,
     16,130,  8,  8,164, 13, 65, 18, 96,192,  0, 36,210, 34, 97,  8,
    132,  4, 27,130,  1,211, 16,  1,  2,160, 68,192, 34, 96,145, 20,
     12, 64,166,  4,210,148, 32,  9,148, 32, 82,  0,  8, 16,162, 76,
      0,130,  1, 81, 16,  8,139,164, 37,154, 48, 68,129, 16, 76,  3,
      2, 37, 82,128,  8, 73,132, 32, 80, 50,  0, 24,162, 64, 17, 36,
     40,  1,132,  1,  1,160, 65, 10, 18, 69,  0, 54,  8,  0, 38, 41,
    131,130, 97,192,128,  4, 16, 16,109,  0, 34, 72, 88, 38, 12,194,
     16, 72,137, 36, 32, 88, 32, 69,136, 36,  0, 25,  2, 37,192, 16,
    104,  8, 20,  1,202, 50, 40,128,  0,  4, 75, 38,  0, 19,144, 96,
    130,128, 37,208,  0,  1, 16, 50, 12, 67,134, 33, 17,  0,  8, 67,
     36,  4, 72, 16, 12,144,146,  0, 67, 32, 45,  0,  6,  9,136, 36,
     64,192, 50,  9,  9,130,  0, 83,128,  8,128,150, 65,129,  0, 64,
     72, 16, 72,  8,150, 72, 88, 32, 41,195,128, 32,  2,148, 96,146,
      0, 32,129, 34, 68, 16,160,  5, 64,144,  1, 73, 32,  4, 10,  0,
     36,137, 52, 72, 19,128, 44,192,130, 41,  0, 36, 69,  8,  0,  8,
    152, 54,  4, 82,132,  4,208,  4,  0,138,144, 68,130, 50,101, 24,
    144,  0, 10,  2,  1, 64,  2, 40, 64,164,  4,146, 48,  4, 17,134,
      8, 66,  0, 44, 82,  4,  8,201,132, 96, 72, 18,  9,153, 36, 68,
      0, 36,  0,  3, 20, 33,  0, 16,  1, 26, 50,  5,136, 32, 64, 64,
      6,  9,195,132, 64,  1, 48, 96, 24,  2,104, 17,144, 12,  2,162,
      4,  0,134, 41,137, 20, 36,130,  2, 65,  8,128,  4, 25,128,  8,
     16, 18,104, 66,164,  4,  0,  2, 97, 16,  6, 12, 16,  0,  1, 18,
     16, 32,  3,148, 33, 66, 18,101, 24,148, 12, 10,  4, 40,  1, 20,
     41, 10,164, 64,208,  0, 64,  1,144,  4, 65, 32, 45, 64,130, 72,
    193, 32,  0, 16, 48,  1,  8, 36,  4, 89,132, 36,  0,  2, 41,130,
      0, 97, 88,  2, 72,129, 22, 72, 16,  0, 33, 17,  6,  0,202,160,
     64,  2,  0,  4,145,176,  0, 66,  4, 12,129,  6,  9, 72, 20, 37,
    146, 32, 37, 17,160,  0, 10,134, 12,193,  2, 72,  0, 32, 69,  8,
     50,  0,152,  6,  4, 19, 34,  0,130,  4, 72,129, 20, 68,130, 18,
     36, 24, 16, 64, 67,128, 40,208,  4, 32,129, 36,100,216,  0, 44,
      9, 18,  8, 65,162,  0,  0,  2, 65,202, 32, 65,192, 16,  1, 24,
    164,  4, 24,164, 32, 18,148, 32,131,160, 64,  2, 50, 68,128,  4,
      0, 24,  0, 12, 64,134, 96,138,  0,100,136, 18,  5,  1,130,  0,
     74,162,  1,193, 16, 97,  9,  4,  1,136,  0, 96,  1,180, 64,  8,
      6,  1,  3,128,  8, 64,148,  4,138, 32, 41,128,  2, 12, 82,  2,
      1, 66,132,  0,128,132,100,  2, 50, 72,  0, 48, 68, 64, 34, 33,
      0,  2,  8,195,160,  4,208, 32, 64, 24, 22, 64, 64,  0, 40, 82,
    144,  8,130, 20,  1, 24, 16,  8,  9,130, 64, 10,160, 32,147,128,
      8,192,  0, 32, 82,  0,  5,  1, 16, 64, 17,  6, 12,130,  0,  0,
     75,144, 68,154,  0, 40,128,144,  4, 74,  6,  9, 67,  2, 40,  0,
     52,  1, 24,  0,101,  9,128, 68,  3,  0, 36,  2,130, 97, 72, 20,
     65,  0, 18, 40,  0, 52,  8, 81,  4,  5, 18,144, 40,137,132, 96,
     18, 16, 73, 16, 38, 64, 73,130,  0,145, 16,  1, 10, 36, 64,136,
     16, 76, 16,  4,  0, 80,162, 44, 64,144, 72, 10,176,  1, 80, 18,
      8,  0,164,  4,  9,160, 40,146,  2,  0, 67, 16, 33,  2, 32, 65,
    129, 50,  0,  8,  4, 12, 82,  0, 33, 73,132, 32, 16,  2,  1,129,
     16, 72, 64, 34,  1,  1,132,105,193, 48,  1,200,  2, 68,136,  0,
     12,  1,  2, 45,192, 18, 97,  0,160,  0,192, 48, 64,  1, 18,  8,
     11, 32,  0,128,148, 64,  1,132, 64,  0, 50,  0, 16,132,  0, 11,
     36,  0,  1,  6, 41,138,132, 65,128, 16,  8,  8,148, 76,  3,128,
      1, 64,150, 64, 65, 32, 32, 80, 34, 37,137,162, 64, 64,164, 32,
      2,134, 40,  1, 32, 33, 74, 16,  8,  0, 20,  8, 64,  4, 37, 66,
      2, 33, 67, 16,  4,146,  0, 33, 17,160, 76, 24, 34,  9,  3,132,
     65,137, 16,  4,130, 34, 36,  1, 20,  8,  8,132,  8,193,  0,  9,
     66,176, 65,138,  2,  0,128, 54,  4, 73,160, 36,145,  0,  0,  2,
    148, 65,146,  2,  1,  8,  6,  8,  9,  0,  1,208, 22, 40,137,128,
     96,  0,  0,104,  1,144, 12, 80, 32,  1, 64,128, 64, 66, 48, 65,
      0, 32, 37,129,  6, 64, 73,  0,  8,  1, 18, 73,  0,160, 32, 24,
     48,  5,  1,166,  0, 16, 36, 40,  0,  2, 32,200, 32,  0,136, 18,
     12,144,146,  0,  2, 38,  1, 66, 22, 73,  0,  4, 36, 66,  2,  1,
    136,128, 12, 26,128,  8, 16,  0, 96,  2,148, 68,136,  0,105, 17,
     48,  8, 18,160, 36, 19,132,  0,130,  0,101,192, 16, 40,  0, 48,
      4,  3, 32,  1, 17,  6,  1,200,128,  0,194, 32,  8, 16,130, 12,
     19,  2, 12, 82,  6, 64,  0,176, 97, 64, 16,  1,152,134,  4, 16,
    132,  8,146, 20, 96, 65,128, 65, 26, 16,  4,129, 34, 64, 65, 32,
     41, 82,  0, 65,  8, 52, 96, 16,  0, 40,  1, 16, 64,  0,132,  8,
     66,144, 32, 72,  4,  4, 82,  2,  0,  8, 32,  4,  0,130, 13,  0,
    130, 64,  2, 16,  5, 72, 32, 64,153,  0,  0,  1,  6, 36,192,  0,
    104,130,  4, 33, 18, 16, 68,  8,  4,  0, 64,166, 32,208, 22,  9,
    201, 36, 65,  2, 32, 12,  9,146, 64, 18,  0,  0, 64,  0,  9, 67,
    132, 32,152,  2,  1, 17, 36,  0, 67, 36,  0,  3,144,  8, 65, 48,
     36, 88, 32, 76,128,130,  8, 16, 36, 37,129,  6, 65,  9, 16, 32,
     24, 16, 68,128, 16,  0, 74, 36, 13,  1,148, 40,128, 48,  0,192,
      2, 96, 16,132, 12,  2,  0,  9,  2,130,  1,  8, 16,  4,194, 32,
    104,  9,  6,  4, 24,  0,  0, 17,144,  8, 11, 16, 33,130,  2, 12,
     16,182,  8,  0, 38,  0, 65,  2,  1, 74, 36, 33, 26, 32, 36,128,
      0, 68,  2,  0, 45, 64,  2,  0,139,148, 32, 16,  0, 32,144,166,
     64, 19,  0, 44, 17,134, 97,  1,128, 65, 16,  2,  4,129, 48, 72,
     72, 32, 40, 80,128, 33,138, 16,  4,  8, 16,  9, 16, 16, 72, 66,
    160, 12,130,146, 96,192, 32,  5,210, 32, 64,  1,  0,  4,  8,130,
     45,130,  2,  0, 72,128, 65, 72, 16,  0,145,  4,  4,  3,132,  0,
    194,  4,104,  0,  0,100,192, 34, 64,  8, 50, 68,  9,134,  0,145,
      2, 40,  1,  0,100, 72,  0, 36, 16,144,  0, 67,  0, 33, 82,134,
     65,139,144, 32, 64, 32,  8,136,  4, 68, 19, 32,  0,  2,132, 96,
    129,144, 36, 64, 48,  0,  8, 16,  8,  8,  2,  1, 16,  4, 32, 67,
    180, 64,144, 18,104,  1,128, 76, 24,  0,  8,192, 18, 73, 64, 16,
     36, 26,  0, 65,137, 36, 76, 16,  0,  4, 82, 16,  9, 74, 32, 65,
     72, 34,105, 17, 20,  8, 16,  6, 36,128,132, 40,  0, 16,  0, 64,
     16,  1,  8, 38,  8, 72,  6, 40,  0, 20,  1, 66,132,  4, 10, 32,
      0,  1,130,  8,  0,130, 36, 18,  4, 64, 64,160, 64,144, 16,  4,
    144, 34, 64, 16, 32, 44,128, 16, 40, 67,  0,  4, 88,  0,  1,129,
     16, 72,  9, 32, 33,131,  4,  0, 66,164, 68,  0,  0,108, 16,160,
     68, 72,128,  0,131,128, 72,201,  0,  0,  0,  2,  5, 16,176,  4,
     19,  4, 41, 16,146, 64,  8,  4, 68,130, 34,  0, 25, 32,  0, 25,
     32,  1,129,144, 96,138,  0, 65,192,  2, 69, 16,  4,  0,  2,162,
      9, 64, 16, 33, 73, 32,  1, 66, 48, 44,  0, 20, 68,  1, 34,  4,
      2,146,  8,137,  4, 33,128, 16,  5,  1, 32, 64, 65,128,  4,  0,
     18,  9, 64,176,100, 88, 50,  1,  8,144,  0, 65,  4,  9,193,128,
     97,  8,144,  0,154,  0, 36,  1, 18,  8,  2, 38,  5,130,  6,  8,
      8,  0, 32, 72, 32,  0, 24, 36, 72,  3,  2,  0, 17,  0,  9,  0,
    132,  1, 74, 16,  1,152,  0,  4, 24,134,  0,192,  0, 32,129,128,
      4, 16, 48,  5,  0,180, 12, 74,130, 41,145,  2, 40,  0, 32, 68,
    192,  0, 44,145,128, 64,  1,162,  0, 18,  4,  9,195, 32,  0,  8,
      2, 12, 16, 34,  4,  0,  0, 44, 17,134,  0,192,  0,  0, 18, 50,
     64,137,128, 64, 64,  2,  5, 80,134, 96,130,164, 96, 10, 18, 77,
    128,144,  8, 18,128,  9,  2, 20, 72,  1, 36, 32,138,  0, 68,144,
      4,  4,  1,  2,  0,209, 18,  0, 10,  4, 64,  0, 50, 33,129, 36,
      8, 25,132, 32,  2,  4,  8,137,128, 36,  2,  2,104, 24,130, 68,
     66,  0, 33, 64,  0, 40,  1,128, 69,130, 32, 64, 17,128, 12,  2,
      0, 36, 64,144,  1, 64, 32, 32, 80, 32, 40, 25,  0, 64,  9, 32,
      8,128,  4, 96, 64,128, 32,  8, 48, 73,  9, 52,  0, 17, 36, 36,
    130,  0, 65,194,  0,  4,146,  2, 36,128,  0, 12,  2,160,  0,  1,
      6, 96, 65,  4, 33,208,  0,  1,  1,  0, 72, 18,132,  4,145, 18,
      8,  0, 36, 68,  0, 18, 65, 24, 38, 12, 65,128,  0, 82,  4, 32,
      9,  0, 36,144, 32, 72, 24,  2,  0,  3,162,  9,208, 20,  0,138,
    132, 37, 74,  0, 32,152, 20, 64,  0,162,  5,  0,  0,  0, 64, 20,
      1, 88, 32, 44,128,132,  0,  9, 32, 32,145,  2,  8,  2,176, 65,
      8, 48,  0,  9, 16,  0, 24,  2, 33,  2,  2,  0,  0, 36, 68,  8,
     18, 96,  0,178, 68, 18,  2, 12,192,128, 64,200, 32,  4, 80, 32,
      5,  0,176,  4, 11,  4, 41, 83,  0, 97, 72, 48,  0,130, 32, 41,
      0, 22,  0, 83, 34, 32, 67, 16, 72,  0,128,  4,210,  0, 64,  0,
    162, 68,  3,128, 41,  0,  4,  8,192,  4,100, 64, 48, 40,  9,132,
     68, 80,128, 33,  2,146,  0,192, 16, 96,136, 34,  8,128,  0,  0,
     24,132,  4,131,150,  0,129, 32,  5,  2,  0, 69,136,132,  0, 81,
     32, 32, 81,134, 65, 75,148,  0,128,  0,  8, 17, 32, 76, 88,128,