LXR toybox/toys/other/factor.c

   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