Imported and adapted from FreeBSD svn r272166 and r272207; this fixes

false positives for products of primes larger than 2^16. For example,
before this commit:

  $ /usr/games/primes 4295360521 4295360522
  4295360521
but
  $ /usr/games/factor 4295360521
  4295360521: 65539 65539

or
  $ /usr/games/primes 3825123056546413049 3825123056546413050
  3825123056546413049
yet
  $ /usr/games/factor 3825123056546413049
  3825123056546413049: 165479 23115459100831

or
  $ /usr/games/primes 18446744073709551577
  18446744073709551577
although
  $ /usr/games/factor 18446744073709551577
  18446744073709551577: 139646831 132095686967

Incidentally, the above examples show the smallest and largest cases that
were erroneously stated as prime in the range 2^32 .. 3825123056546413049
.. 2^64; the primes(6) program now stops at 3825123056546413050 as
primality tests on larger integers would be by brute force factorization.

In addition, special to the NetBSD version:
. for -d option, skip first difference when start is >65537 as it is incorrect
. corrected usage to mention both the existing -d as well as the new -h option

For original FreeBSD commit message by Colin Percival, see:
http://svnweb.freebsd.org/base?view=revision&revision=272166

2 files changed, 13 insertions, 20 deletions

diff --git a/factor/factor.6 b/factor/factor.6
index 32029eca..c36fcb1f 100644
--- a/factor/factor.6
+++ b/factor/factor.6
@@ -1,4 +1,4 @@
-.\"	$NetBSD: factor.6,v 1.12 2010/05/15 21:22:39 joerg Exp $
+.\"	$NetBSD: factor.6,v 1.13 2014/10/02 21:36:37 ast Exp $
 .\"
 .\" Copyright (c) 1989, 1993
 .\"	The Regents of the University of California.  All rights reserved.
@@ -33,9 +33,7 @@
 .\"	@(#)factor.6	8.1 (Berkeley) 5/31/93
 .\"
 .\"
-.\" By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
-.\"
-.\"   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+.\" By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
 .\"
 .Dd May 15, 2010
 .Dt FACTOR 6
@@ -88,10 +86,7 @@ is compiled without OpenSSL it is limited to the maximum value of
 .Vt unsigned long .
 .Sh DIAGNOSTICS
 Out of range or invalid input results in
-an appropriate error message
-being written to standard error.
-.\".Sh BUGS
-.\".Nm
-.\"cannot handle the
-.\".Dq 10 most wanted
-.\"factor list.
+an appropriate error message to standard error.
+.Sh AUTHORS
+Originally by
+.An Landon Curt Noll .
diff --git a/factor/factor.c b/factor/factor.c
index f2ff2e4b..0af41a14 100644
--- a/factor/factor.c
+++ b/factor/factor.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $	*/
+/*	$NetBSD: factor.c,v 1.27 2014/10/02 21:36:37 ast Exp $	*/
 
 /*
  * Copyright (c) 1989, 1993
@@ -42,16 +42,14 @@ __COPYRIGHT("@(#) Copyright (c) 1989, 1993\
 #if 0
 static char sccsid[] = "@(#)factor.c	8.4 (Berkeley) 5/4/95";
 #else
-__RCSID("$NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $");
+__RCSID("$NetBSD: factor.c,v 1.27 2014/10/02 21:36:37 ast Exp $");
 #endif
 #endif /* not lint */
 
 /*
  * factor - factor a number into primes
  *
- * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
- *
- *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
  *
  * usage:
  *	factor [number] ...
@@ -72,6 +70,7 @@ __RCSID("$NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $");
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
+#include <inttypes.h>
 
 #ifdef HAVE_OPENSSL
 #include <openssl/bn.h>
@@ -93,8 +92,7 @@ static int BN_dec2bn(BIGNUM **a, const char *str);
  * We are able to sieve 2^32-1 because this byte table yields all primes
  * up to 65537 and 65537^2 > 2^32-1.
  */
-extern const ubig prime[];
-extern const ubig *pr_limit;		/* largest prime in the prime array */
+
 #if 0 /* debugging: limit table use to stress the "pollard" code */
 #define pr_limit &prime[0]
 #endif
@@ -198,7 +196,7 @@ main(int argc, char *argv[])
 static void
 pr_fact(BIGNUM *val)
 {
-	const ubig *fact;		/* The factor found. */
+	const uint64_t *fact;		/* The factor found. */
 
 	/* Firewall - catch 0 and 1. */
 	if (BN_is_zero(val) || BN_is_one(val))
@@ -239,7 +237,7 @@ pr_fact(BIGNUM *val)
 
 		/* Divide factor out until none are left. */
 		do {
-			printf(" %lu", *fact);
+			printf(" %" PRIu64, *fact);
 			BN_div_word(val, (BN_ULONG)*fact);
 		} while (BN_mod_word(val, (BN_ULONG)*fact) == 0);