xref: /third_party/toybox/toys/other/factor.c (revision 0f66f451) 
1/* factor.c - Factor integers
2 *
3 * Copyright 2014 Rob Landley <rob@landley.net>
4 *
5 * No standard, but it's in coreutils
6
7USE_FACTOR(NEWTOY(factor, 0, TOYFLAG_USR|TOYFLAG_BIN))
8
9config FACTOR
10  bool "factor"
11  default y
12  help
13    usage: factor NUMBER...
14
15    Factor integers.
16*/
17
18#include "toys.h"
19
20static void factor(char *s)
21{
22  unsigned long long l, ll;
23
24  for (;;) {
25    char *err = s;
26    int dash = 0;
27
28    while(isspace(*s)) s++;
29    if (*s=='-') dash = *s++;
30    if (!*s) return;
31
32    errno = 0;
33    l = strtoull(s, &s, 0);
34    if (errno || (*s && !isspace(*s))) {
35      error_msg("%s: not integer", err);
36      while (*s && !isspace(*s)) s++;
37      continue;
38    }
39
40    printf("-%llu:"+!dash, l);
41
42    // Negative numbers have -1 as a factor
43    if (dash) printf(" -1");
44
45    // Nothing below 4 has factors
46    if (l < 4) {
47      printf(" %llu\n", l);
48      continue;
49    }
50
51    // Special case factors of 2
52    while (l && !(l&1)) {
53      printf(" 2");
54      l >>= 1;
55    }
56
57    // test odd numbers until square is > remainder or integer wrap.
58    for (ll=3; ;ll += 2) {
59      long lll = ll*ll;
60
61      if (lll>l || lll<ll) {
62        if (l>1) printf(" %llu", l);
63        break;
64      }
65      while (!(l%ll)) {
66        printf(" %llu", ll);
67        l /= ll;
68      }
69    }
70    xputc('\n');
71  }
72}
73
74void factor_main(void)
75{
76  if (toys.optc) {
77    char **ss;
78
79    for (ss = toys.optargs; *ss; ss++) factor(*ss);
80  } else for (;;) {
81    char *s = 0;
82    size_t len = 0;
83
84    if (-1 == getline(&s, &len, stdin)) break;
85    factor(s);
86  }
87}
88