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    l = strtoull(s, &s, 0);
33    if (*s && !isspace(*s)) {
34      error_msg("%s: not integer", err);
35      while (*s && !isspace(*s)) s++;
36      continue;
37    }
38
39    printf("-%llu:"+!dash, l);
40
41    // Negative numbers have -1 as a factor
42    if (dash) printf(" -1");
43
44    // Nothing below 4 has factors
45    if (l < 4) {
46      printf(" %llu\n", l);
47      continue;
48    }
49
50    // Special case factors of 2
51    while (l && !(l&1)) {
52      printf(" 2");
53      l >>= 1;
54    }
55
56    // test odd numbers until square is > remainder or integer wrap.
57    for (ll=3; ;ll += 2) {
58      long lll = ll*ll;
59
60      if (lll>l || lll<ll) {
61        if (l>1) printf(" %llu", l);
62        break;
63      }
64      while (!(l%ll)) {
65        printf(" %llu", ll);
66        l /= ll;
67      }
68    }
69    xputc('\n');
70  }
71}
72
73void factor_main(void)
74{
75  if (toys.optc) {
76    char **ss;
77
78    for (ss = toys.optargs; *ss; ss++) factor(*ss);
79  } else for (;;) {
80    char *s = 0;
81    size_t len = 0;
82
83    if (-1 == getline(&s, &len, stdin)) break;
84    factor(s);
85  }
86}
87