1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include "libbb.h"
22
23#if 0
24# define dbg(...) bb_error_msg(__VA_ARGS__)
25#else
26# define dbg(...) ((void)0)
27#endif
28
29typedef unsigned long long wide_t;
30
31#if ULLONG_MAX == (UINT_MAX * UINT_MAX + 2 * UINT_MAX)
32
33typedef unsigned half_t;
34#define HALF_MAX UINT_MAX
35#define HALF_FMT ""
36#elif ULLONG_MAX == (ULONG_MAX * ULONG_MAX + 2 * ULONG_MAX)
37
38typedef unsigned long half_t;
39#define HALF_MAX ULONG_MAX
40#define HALF_FMT "l"
41#else
42#error Cant find an integer type which is half as wide as ullong
43#endif
44
45static half_t isqrt_odd(wide_t N)
46{
47 half_t s = isqrt(N);
48
49
50 s = (s - 1) | 1;
51 return s;
52}
53
54static NOINLINE void factorize(wide_t N)
55{
56 half_t factor;
57 half_t max_factor;
58
59
60
61
62
63
64
65
66
67
68 enum {
69 SHIFT_3 = 1 << 0,
70 SHIFT_5 = 1 << 3,
71 SHIFT_7 = 1 << 7,
72 INCREMENT_EACH = SHIFT_3 | SHIFT_5 | SHIFT_7,
73 MULTIPLE_OF_3 = 1 << 2,
74 MULTIPLE_OF_5 = 1 << 6,
75 MULTIPLE_OF_7 = 1 << 11,
76 MULTIPLE_DETECTED = MULTIPLE_OF_3 | MULTIPLE_OF_5 | MULTIPLE_OF_7,
77 };
78 unsigned sieve_word;
79
80 if (N < 4)
81 goto end;
82
83 while (!(N & 1)) {
84 printf(" 2");
85 N >>= 1;
86 }
87
88
89
90
91
92
93
94
95
96
97
98
99
100 max_factor = isqrt_odd(N);
101
102
103
104 sieve_word = 0
105
106 + (MULTIPLE_OF_3 - 3 * SHIFT_3)
107 + (MULTIPLE_OF_5 - 6 * SHIFT_5)
108 + (MULTIPLE_OF_7 - 9 * SHIFT_7)
109
110
111
112 ;
113 factor = 3;
114 for (;;) {
115
116
117
118 while ((N % factor) == 0) {
119 N = N / factor;
120 printf(" %"HALF_FMT"u", factor);
121 max_factor = isqrt_odd(N);
122 }
123 next_factor:
124 if (factor >= max_factor)
125 break;
126 factor += 2;
127
128
129
130
131
132
133
134
135
136
137
138
139 sieve_word += INCREMENT_EACH;
140 if (!(sieve_word & MULTIPLE_DETECTED))
141 continue;
142
143
144
145
146
147
148
149
150 if (sieve_word & MULTIPLE_OF_3)
151 sieve_word -= SHIFT_3 * 3;
152
153
154 if (sieve_word & MULTIPLE_OF_5)
155 sieve_word -= SHIFT_5 * 5;
156
157
158 if (sieve_word & MULTIPLE_OF_7)
159 sieve_word -= SHIFT_7 * 7;
160 goto next_factor;
161 }
162 end:
163 if (N > 1)
164 printf(" %llu", N);
165 bb_putchar('\n');
166}
167
168static void factorize_numstr(const char *numstr)
169{
170 wide_t N;
171
172
173 if (*numstr == '+')
174 numstr++;
175 N = bb_strtoull(numstr, NULL, 10);
176 if (errno)
177 bb_show_usage();
178 printf("%llu:", N);
179 factorize(N);
180}
181
182int factor_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
183int factor_main(int argc UNUSED_PARAM, char **argv)
184{
185
186
187
188 argv++;
189
190 if (!*argv) {
191
192 for (;;) {
193 char *numstr, *line;
194 line = xmalloc_fgetline(stdin);
195 if (!line)
196 return EXIT_SUCCESS;
197 numstr = line;
198 for (;;) {
199 char *end;
200 numstr = skip_whitespace(numstr);
201 if (!numstr[0])
202 break;
203 end = skip_non_whitespace(numstr);
204 if (*end != '\0')
205 *end++ = '\0';
206 factorize_numstr(numstr);
207 numstr = end;
208 }
209 free(line);
210 }
211 }
212
213 do {
214
215 factorize_numstr(skip_whitespace(*argv));
216 } while (*++argv);
217
218 return EXIT_SUCCESS;
219}
220