diff options
| -rw-r--r-- | coreutils/factor.c | 112 | ||||
| -rwxr-xr-x | testsuite/factor.tests | 48 |
2 files changed, 160 insertions, 0 deletions
diff --git a/coreutils/factor.c b/coreutils/factor.c new file mode 100644 index 000000000..0f838a735 --- /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); +} diff --git a/testsuite/factor.tests b/testsuite/factor.tests new file mode 100755 index 000000000..2cf4a54ce --- /dev/null +++ b/testsuite/factor.tests @@ -0,0 +1,48 @@ +#!/bin/sh + +# Copyright 2017 by Denys Vlasenko <vda.linux@googlemail.com> +# Licensed under GPLv2, see file LICENSE in this source tree. + +. ./testing.sh + +# testing "test name" "command" "expected result" "file input" "stdin" +# file input will be file called "input" +# test can create a file "actual" instead of writing to stdout + +testing "factor ' 0'" \ + "factor ' 0'" \ + "0:\n" \ + "" "" +testing "factor +1" \ + "factor +1" \ + "1:\n" \ + "" "" +testing "factor ' +2'" \ + "factor ' +2'" \ + "2: 2\n" \ + "" "" + +testing "factor 1024" \ + "factor 1024" \ + "1024: 2 2 2 2 2 2 2 2 2 2\n" \ + "" "" + +testing "factor 2^61-1" \ + "factor 2305843009213693951" \ + "2305843009213693951: 2305843009213693951\n" \ + "" "" +testing "factor 2^62-1" \ + "factor 4611686018427387903" \ + "4611686018427387903: 3 715827883 2147483647\n" \ + "" "" +testing "factor 2^64-1" \ + "factor 18446744073709551615" \ + "18446744073709551615: 3 5 17 257 641 65537 6700417\n" \ + "" "" +# This is a 60-bit number (0x888 86ff db34 4692): first few primes multiplied together: +testing "factor \$((2*3*5*7*11*13*17*19*23*29*31*37*41*43*47))" \ + "factor \$((2*3*5*7*11*13*17*19*23*29*31*37*41*43*47))" \ + "614889782588491410: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47\n" \ + "" "" + +exit $FAILCOUNT |