Mercurial > hg > toybox
annotate toys/other/factor.c @ 1411:dd336488a69b draft
factor: catch integer overflow.
Now factor 9223372036854775783 (largest positive 64 bit signed prime) takes a
couple minutes but gives the right answer.
| author | Rob Landley <rob@landley.net> |
|---|---|
| date | Fri, 01 Aug 2014 18:50:46 -0500 |
| parents | ee0109c35b34 |
| children | 89384d54d49a |
| rev | line source |
|---|---|
| 1410 | 1 /* factor.c - Factor integers |
| 2 * | |
| 3 * Copyright 2014 Rob Landley <rob@landley.net> | |
| 4 * | |
| 5 * No standard, but it's in coreutils | |
| 6 | |
| 7 USE_FACTOR(NEWTOY(factor, 0, TOYFLAG_USR|TOYFLAG_BIN)) | |
| 8 | |
| 9 config FACTOR | |
| 10 bool "factor" | |
| 11 default y | |
| 12 help | |
| 13 usage: factor NUMBER... | |
| 14 | |
| 15 Factor integers. | |
| 16 */ | |
| 17 | |
| 18 #include "toys.h" | |
| 19 | |
| 20 static void factor(char *s) | |
| 21 { | |
| 22 long l, ll; | |
| 23 | |
| 24 l = strtol(s, &s, 0); | |
| 25 if (*s) { | |
| 26 error_msg("%s: not integer"); | |
| 27 return; | |
| 28 } | |
| 29 | |
| 30 printf("%ld:", l); | |
| 31 | |
| 32 // Negative numbers have -1 as a factor | |
| 33 if (l < 0) { | |
| 34 printf(" -1"); | |
| 35 l *= -1; | |
| 36 } | |
| 37 | |
| 38 // Deal with 0 and 1 (and 2 since we're here) | |
| 39 if (l < 3) { | |
| 40 printf(" %ld\n", l); | |
| 41 return; | |
| 42 } | |
| 43 | |
| 44 // Special case factors of 2 | |
| 45 while (l && !(l&1)) { | |
| 46 printf(" 2"); | |
| 47 l >>= 1; | |
| 48 } | |
| 49 | |
| 50 // test odd numbers. | |
| 51 for (ll=3; ;ll += 2) { | |
|
1411
dd336488a69b
factor: catch integer overflow.
Rob Landley <rob@landley.net>
parents:
1410
diff
changeset
|
52 long lll = ll*ll; |
|
dd336488a69b
factor: catch integer overflow.
Rob Landley <rob@landley.net>
parents:
1410
diff
changeset
|
53 |
|
dd336488a69b
factor: catch integer overflow.
Rob Landley <rob@landley.net>
parents:
1410
diff
changeset
|
54 if (lll>l || lll<ll) { |
| 1410 | 55 if (l>1) printf(" %ld", l); |
| 56 break; | |
| 57 } | |
| 58 while (!(l%ll)) { | |
| 59 printf(" %ld", ll); | |
| 60 l /= ll; | |
| 61 } | |
| 62 } | |
| 63 xputc('\n'); | |
| 64 } | |
| 65 | |
| 66 void factor_main(void) | |
| 67 { | |
| 68 if (toys.optc) { | |
| 69 char **ss; | |
| 70 | |
| 71 for (ss = toys.optargs; *ss; ss++) factor(*ss); | |
| 72 } else for (;;) { | |
| 73 char *s = 0; | |
| 74 size_t len = 0; | |
| 75 | |
| 76 if (-1 == getline(&s, &len, stdin)) break; | |
| 77 factor(s); | |
| 78 } | |
| 79 } |