From ee7f75d94f2a70d61a71eca9416d51a3268859d7 Mon Sep 17 00:00:00 2001
From: Denys Vlasenko
Date: Sun, 9 Apr 2017 21:18:43 +0200
Subject: factor: new applet
thus far only able to factor up to ULLONG_MAX
function old new delta
factor_main - 378 +378
packed_usage 31427 31502 +75
applet_names 2590 2597 +7
applet_main 1500 1504 +4
------------------------------------------------------------------------------
(add/remove: 2/0 grow/shrink: 3/0 up/down: 464/0) Total: 464 bytes
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
---
coreutils/factor.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 112 insertions(+)
create mode 100644 coreutils/factor.c
(limited to 'coreutils')
diff --git a/coreutils/factor.c b/coreutils/factor.c
new file mode 100644
index 0000000..0f838a7
--- /dev/null
+++ b/coreutils/factor.c
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2017 Denys Vlasenko <vda.linux@googlemail.com>
+ *
+ * Licensed under GPLv2, see file LICENSE in this source tree.
+ */
+//config:config FACTOR
+//config: bool "factor"
+//config: default y
+//config: help
+//config: factor factorizes integers
+
+//applet:IF_FACTOR(APPLET(factor, BB_DIR_USR_BIN, BB_SUID_DROP))
+
+//kbuild:lib-$(CONFIG_FACTOR) += factor.o
+
+//usage:#define factor_trivial_usage
+//usage: "NUMBER..."
+//usage:#define factor_full_usage "\n\n"
+//usage: "Print prime factors"
+
+#include "libbb.h"
+
+#if ULLONG_MAX == (UINT_MAX * UINT_MAX + 2 * UINT_MAX)
+/* "unsigned" is half as wide as ullong */
+typedef unsigned half_t;
+#define HALF_FMT ""
+#elif ULLONG_MAX == (ULONG_MAX * ULONG_MAX + 2 * ULONG_MAX)
+/* long is half as wide as ullong */
+typedef unsigned long half_t;
+#define HALF_FMT "l"
+#else
+#error Cant find an integer type which is half as wide as ullong
+#endif
+
+static void factorize(const char *numstr)
+{
+ unsigned long long N, factor2;
+ half_t factor;
+ unsigned count3;
+
+ /* Coreutils compat */
+ numstr = skip_whitespace(numstr);
+ if (*numstr == '+')
+ numstr++;
+
+ N = bb_strtoull(numstr, NULL, 10);
+ if (errno)
+ bb_show_usage();
+
+ printf("%llu:", N);
+
+ if (N < 4)
+ goto end;
+ while (!(N & 1)) {
+ printf(" 2");
+ N >>= 1;
+ }
+
+ count3 = 3;
+ factor = 3;
+ factor2 = 3 * 3;
+ for (;;) {
+ unsigned long long nfactor2;
+
+ while ((N % factor) == 0) {
+ N = N / factor;
+ printf(" %u"HALF_FMT"", factor);
+ }
+ next_factor:
+ /* (f + 2)^2 = f^2 + 4*f + 4 = f^2 + 4*(f+1) */
+ nfactor2 = factor2 + 4 * (factor + 1);
+ if (nfactor2 < factor2) /* overflow? */
+ break;
+ factor2 = nfactor2;
+ if (factor2 > N)
+ break;
+ factor += 2;
+ /* Rudimentary wheel sieving: skip multiples of 3:
+ * Every third odd number is divisible by three and thus isn't a prime:
+ * 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37...
+ * ^ ^ ^ ^ ^ ^ ^ _ ^ ^ _ ^ (^primes)
+ */
+ --count3;
+ if (count3 == 0) {
+ count3 = 3;
+ goto next_factor;
+ }
+ }
+ end:
+ if (N > 1)
+ printf(" %llu", N);
+ bb_putchar('\n');
+}
+
+int factor_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
+int factor_main(int argc UNUSED_PARAM, char **argv)
+{
+ //// coreutils has undocumented option ---debug (three dashes)
+ //getopt32(argv, "");
+ //argv += optind;
+ argv++;
+
+ if (!*argv)
+ //TODO: read from stdin
+ bb_show_usage();
+
+ do {
+ factorize(*argv);
+ } while (*++argv);
+
+ fflush_stdout_and_exit(EXIT_SUCCESS);
+}
--
cgit v1.1