Fix merge conflicts

[bsdgames-darwin.git] / primes / primes.h

diff --git a/primes/primes.h b/primes/primes.h
index 3cc34a20cec35e95574a688ba5a3ca66e784156d..2c004465f9b211df1281715eafd5b46a317f274b 100644 (file)
--- a/primes/primes.h
+++ b/primes/primes.h
@@ -1,6 +1,8 @@
+/*     $NetBSD: primes.h,v 1.7 2018/02/03 15:40:29 christos Exp $      */
+
 /*
- * Copyright (c) 1989 The Regents of the University of California.
- * All rights reserved.
+ * Copyright (c) 1989, 1993
+ *     The Regents of the University of California.  All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by
  * Landon Curt Noll.
@@ -13,11 +15,7 @@
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *     This product includes software developed by the University of
- *     California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
+ * 3. Neither the name of the University nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  *
@@ -33,24 +31,41 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *     @(#)primes.h    5.2 (Berkeley) 6/1/90
+ *     @(#)primes.h    8.2 (Berkeley) 3/1/94
  */
 
 /*
  * primes - generate a table of primes between two values
  *
- * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
  *
- *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
  */
 
-/* ubig is the type that holds a large unsigned value */
-typedef unsigned long ubig;           /* must be >=32 bit unsigned value */
+#include <stdint.h>
+
+/* bytes in sieve table (must be > 3*5*7*11) */
+#define        TABSIZE         256*1024
 
 /*
- * sieve parameters
+ * prime[i] is the (i-1)th prime.
+ *
+ * We are able to sieve 2^32-1 because this byte table yields all primes
+ * up to 65537 and 65537^2 > 2^32-1.
  */
-#define BIG ((ubig)0xffffffff)        /* highest value we will sieve */
-#define SEMIBIG ((ubig)0x7fffffff)    /* highest signed value */
-#define NEG_SEMIBIG ((ubig)0x80000000) /* lowest signed value */
-#define TABSIZE 256*1024 /* bytes in sieve table (must be > 3*5*7*11) */
+
+extern const uint64_t prime[];         /* must be >=32 bit unsigned values */
+extern const uint64_t *const pr_limit; /* largest prime in the prime array */
+
+/* Maximum size sieving alone can handle. */
+#define        SIEVEMAX 4295098368ULL
+
+/*
+ * To avoid excessive sieves for small factors, we use the table below to
+ * setup our sieve blocks.  Each element represents an odd number starting
+ * with 1.  All non-zero elements are factors of 3, 5, 7, 11 and 13.
+ */
+extern const char pattern[];
+extern const size_t pattern_size;      /* length of pattern array */
+
+/* Test for primality using strong pseudoprime tests. */
+int isprime(uint64_t);