divisibilityprime factorization
I know that one way to find the number of divisors is to find the prime factors of that number and add one to all of the powers and then multiply them together so for example
$$555 = 3^1 \cdot 5^1 \cdot 37^1$$
therefore the number of divisors = $(1+1)(1+1)(1+1) = 2 \cdot 2 \cdot 2 = 8$
What I do not know (and can't seem to find when I look) is WHY this relationship exists or a formula which shows its proof.
Has anyone seen such a formula?
The logic is simple:
Hence there are $5\cdot2=10$ divisors:
I am addressing the question of finding the smallest number with AT LEAST $N$ divisors. Trying to get exactly $N$ divisors is a different level of nightmare.
well, i cannot tell how much work you are willing to put into this. Guy Robin came up with a method for finding the highly composite numbers between two consecutitive superior highly composite numbers.
Assuming that is too ambitious, do this: first find the first primorial number $P =2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdots p_k$ that has more divisors than you need. That would mean $2^k$ is larger than you want.
Next, make a fairly complicated multiple loop to produce all the numbers $$ 2^{e_2} 3^{e_3} 5^{e_5} \cdots p_k^{e_{p_k}} \; \leq \; \; P $$ WITH $$ e_2 \geq e_3 \geq e_5 \geq \ldots \geq e_{p_k} \geq 0 $$ then calculate the number of divisors ( depends only on the exponents) and calculate the number itself.
The winner, smallest such number with at least some $N$ divisors, is likely to have a number of exponents zero at the end. The general pattern is that highly composite numbers are fairly similar to the least common multiple $L$ of $1,2,3,4,5,6,7,\ldots, w$ as far as the relative sizes of the prime exponents when the whole thing is factored. I should point out that the prime number theorem says $\log L \approx W.$
A little more efficiency: we can combine the two bounds. We can find the smallest LCM $L$ that has enough divisors. This will give a better (smaller) upper bound. Then, using the set of primes we used in producing the primorial $P,$ we can produce all the numbers $$ 2^{e_2} 3^{e_3} 5^{e_5} \cdots p_k^{e_{p_k}} \; \leq \; \; L $$ WITH $$ e_2 \geq e_3 \geq e_5 \geq \ldots \geq e_{p_k} \geq 0 $$
===================================
Fri Apr 27 11:08:30 PDT 2018
Fri Apr 27 11:08:56 PDT 2018
d(n) n factored
1 1 = 1
2 2 = 2
3 4 = 2^2
4 6 = 2 3
4 8 = 2^3
5 16 = 2^4
6 12 = 2^2 3
6 32 = 2^5
7 64 = 2^6
8 128 = 2^7
8 24 = 2^3 3
8 30 = 2 3 5
9 256 = 2^8
9 36 = 2^2 3^2
10 48 = 2^4 3
10 512 = 2^9
11 1024 = 2^10
12 2048 = 2^11
12 60 = 2^2 3 5
12 72 = 2^3 3^2
12 96 = 2^5 3
13 4096 = 2^12
14 192 = 2^6 3
14 8192 = 2^13
15 144 = 2^4 3^2
15 16384 = 2^14
16 120 = 2^3 3 5
16 210 = 2 3 5 7
16 216 = 2^3 3^3
16 32768 = 2^15
16 384 = 2^7 3
17 65536 = 2^16
18 131072 = 2^17
18 180 = 2^2 3^2 5
18 288 = 2^5 3^2
18 768 = 2^8 3
19 262144 = 2^18
20 1536 = 2^9 3
20 240 = 2^4 3 5
20 432 = 2^4 3^3
20 524288 = 2^19
21 1048576 = 2^20
21 576 = 2^6 3^2
22 2097152 = 2^21
22 3072 = 2^10 3
23 4194304 = 2^22
24 1152 = 2^7 3^2
24 360 = 2^3 3^2 5
24 420 = 2^2 3 5 7
24 480 = 2^5 3 5
24 6144 = 2^11 3
24 8388608 = 2^23
24 864 = 2^5 3^3
25 1296 = 2^4 3^4
26 12288 = 2^12 3
27 2304 = 2^8 3^2
27 900 = 2^2 3^2 5^2
28 1728 = 2^6 3^3
28 24576 = 2^13 3
28 960 = 2^6 3 5
30 2592 = 2^5 3^4
30 4608 = 2^9 3^2
30 49152 = 2^14 3
30 720 = 2^4 3^2 5
32 1080 = 2^3 3^3 5
32 1920 = 2^7 3 5
32 2310 = 2 3 5 7 11
32 3456 = 2^7 3^3
32 840 = 2^3 3 5 7
32 98304 = 2^15 3
33 9216 = 2^10 3^2
34 196608 = 2^16 3
35 5184 = 2^6 3^4
36 1260 = 2^2 3^2 5 7
36 1440 = 2^5 3^2 5
36 1800 = 2^3 3^2 5^2
36 18432 = 2^11 3^2
36 3840 = 2^8 3 5
36 393216 = 2^17 3
36 6912 = 2^8 3^3
36 7776 = 2^5 3^5
38 786432 = 2^18 3
39 36864 = 2^12 3^2
40 10368 = 2^7 3^4
40 13824 = 2^9 3^3
40 1572864 = 2^19 3
40 1680 = 2^4 3 5 7
40 2160 = 2^4 3^3 5
40 7680 = 2^9 3 5
42 15552 = 2^6 3^5
42 2880 = 2^6 3^2 5
42 3145728 = 2^20 3
42 73728 = 2^13 3^2
44 15360 = 2^10 3 5
44 27648 = 2^10 3^3
44 6291456 = 2^21 3
45 147456 = 2^14 3^2
45 20736 = 2^8 3^4
45 3600 = 2^4 3^2 5^2
48 2520 = 2^3 3^2 5 7
48 294912 = 2^15 3^2
48 30720 = 2^11 3 5
48 31104 = 2^7 3^5
48 3360 = 2^5 3 5 7
48 4320 = 2^5 3^3 5
48 4620 = 2^2 3 5 7 11
48 5400 = 2^3 3^3 5^2
48 55296 = 2^11 3^3
48 5760 = 2^7 3^2 5
49 46656 = 2^6 3^6
50 41472 = 2^9 3^4
50 6480 = 2^4 3^4 5
51 589824 = 2^16 3^2
52 110592 = 2^12 3^3
52 61440 = 2^12 3 5
54 11520 = 2^8 3^2 5
54 1179648 = 2^17 3^2
54 62208 = 2^8 3^5
54 6300 = 2^2 3^2 5^2 7
54 7200 = 2^5 3^2 5^2
55 82944 = 2^10 3^4
56 122880 = 2^13 3 5
56 221184 = 2^13 3^3
56 6720 = 2^6 3 5 7
56 8640 = 2^6 3^3 5
56 93312 = 2^7 3^6
57 2359296 = 2^18 3^2
60 10800 = 2^4 3^3 5^2
60 124416 = 2^9 3^5
60 12960 = 2^5 3^4 5
60 165888 = 2^11 3^4
60 23040 = 2^9 3^2 5
60 245760 = 2^14 3 5
60 442368 = 2^14 3^3
60 4718592 = 2^19 3^2
60 5040 = 2^4 3^2 5 7
63 14400 = 2^6 3^2 5^2
63 186624 = 2^8 3^6
63 9437184 = 2^20 3^2
64 13440 = 2^7 3 5 7
64 17280 = 2^7 3^3 5
64 27000 = 2^3 3^3 5^3
64 279936 = 2^7 3^7
64 30030 = 2 3 5 7 11 13
64 491520 = 2^15 3 5
64 7560 = 2^3 3^3 5 7
64 884736 = 2^15 3^3
64 9240 = 2^3 3 5 7 11
65 331776 = 2^12 3^4
66 248832 = 2^10 3^5
66 46080 = 2^10 3^2 5
68 1769472 = 2^16 3^3
68 983040 = 2^16 3 5
70 25920 = 2^6 3^4 5
70 373248 = 2^9 3^6
70 663552 = 2^13 3^4
72 10080 = 2^5 3^2 5 7
72 12600 = 2^3 3^2 5^2 7
72 13860 = 2^2 3^2 5 7 11
72 1966080 = 2^17 3 5
72 21600 = 2^5 3^3 5^2
72 26880 = 2^8 3 5 7
72 28800 = 2^7 3^2 5^2
72 34560 = 2^8 3^3 5
72 3538944 = 2^17 3^3
72 38880 = 2^5 3^5 5
72 497664 = 2^11 3^5
72 559872 = 2^8 3^7
72 92160 = 2^11 3^2 5
75 1327104 = 2^14 3^4
75 32400 = 2^4 3^4 5^2
76 3932160 = 2^18 3 5
76 7077888 = 2^18 3^3
77 746496 = 2^10 3^6
78 184320 = 2^12 3^2 5
78 995328 = 2^12 3^5
80 1119744 = 2^9 3^7
80 15120 = 2^4 3^3 5 7
80 18480 = 2^4 3 5 7 11
80 2654208 = 2^15 3^4
80 51840 = 2^7 3^4 5
80 53760 = 2^9 3 5 7
80 54000 = 2^4 3^3 5^3
80 69120 = 2^9 3^3 5
80 7864320 = 2^19 3 5
81 1679616 = 2^8 3^8
81 44100 = 2^2 3^2 5^2 7^2
81 57600 = 2^8 3^2 5^2
84 1492992 = 2^11 3^6
84 1990656 = 2^13 3^5
84 20160 = 2^6 3^2 5 7
84 368640 = 2^13 3^2 5
84 43200 = 2^6 3^3 5^2
84 77760 = 2^6 3^5 5
85 5308416 = 2^16 3^4
88 107520 = 2^10 3 5 7
88 138240 = 2^10 3^3 5
88 2239488 = 2^10 3^7
90 103680 = 2^8 3^4 5
90 115200 = 2^9 3^2 5^2
90 25200 = 2^4 3^2 5^2 7
90 3359232 = 2^9 3^8
90 3981312 = 2^14 3^5
90 64800 = 2^5 3^4 5^2
90 737280 = 2^14 3^2 5
91 2985984 = 2^12 3^6
96 108000 = 2^5 3^3 5^3
96 1474560 = 2^15 3^2 5
96 155520 = 2^7 3^5 5
96 215040 = 2^11 3 5 7
96 276480 = 2^11 3^3 5
96 27720 = 2^3 3^2 5 7 11
96 30240 = 2^5 3^3 5 7
96 36960 = 2^5 3 5 7 11
96 37800 = 2^3 3^3 5^2 7
96 40320 = 2^7 3^2 5 7
96 4478976 = 2^11 3^7
96 60060 = 2^2 3 5 7 11 13
96 7962624 = 2^15 3^5
96 86400 = 2^7 3^3 5^2
98 233280 = 2^6 3^6 5
98 5971968 = 2^13 3^6
99 230400 = 2^10 3^2 5^2
99 6718464 = 2^10 3^8
100 162000 = 2^4 3^4 5^3
100 207360 = 2^9 3^4 5
100 45360 = 2^4 3^4 5 7
102 2949120 = 2^16 3^2 5
104 430080 = 2^12 3 5 7
104 552960 = 2^12 3^3 5
104 8957952 = 2^12 3^7
105 129600 = 2^6 3^4 5^2
108 172800 = 2^8 3^3 5^2
108 194400 = 2^5 3^5 5^2
108 311040 = 2^8 3^5 5
108 460800 = 2^11 3^2 5^2
108 50400 = 2^5 3^2 5^2 7
108 5898240 = 2^17 3^2 5
108 69300 = 2^2 3^2 5^2 7 11
108 80640 = 2^8 3^2 5 7
108 88200 = 2^3 3^2 5^2 7^2
110 414720 = 2^10 3^4 5
112 1105920 = 2^13 3^3 5
112 216000 = 2^6 3^3 5^3
112 466560 = 2^7 3^6 5
112 60480 = 2^6 3^3 5 7
112 73920 = 2^6 3 5 7 11
112 860160 = 2^13 3 5 7
117 921600 = 2^12 3^2 5^2
120 161280 = 2^9 3^2 5 7
120 1720320 = 2^14 3 5 7
120 2211840 = 2^14 3^3 5
120 259200 = 2^7 3^4 5^2
120 324000 = 2^5 3^4 5^3
120 345600 = 2^9 3^3 5^2
120 55440 = 2^4 3^2 5 7 11
120 622080 = 2^9 3^5 5
120 75600 = 2^4 3^3 5^2 7
120 829440 = 2^11 3^4 5
120 90720 = 2^5 3^4 5 7
125 810000 = 2^4 3^4 5^4
126 100800 = 2^6 3^2 5^2 7
126 1843200 = 2^13 3^2 5^2
126 388800 = 2^6 3^5 5^2
126 933120 = 2^8 3^6 5
128 120120 = 2^3 3 5 7 11 13
128 120960 = 2^7 3^3 5 7
128 1399680 = 2^7 3^7 5
128 147840 = 2^7 3 5 7 11
128 189000 = 2^3 3^3 5^3 7
128 3440640 = 2^15 3 5 7
128 432000 = 2^7 3^3 5^3
128 4423680 = 2^15 3^3 5
128 510510 = 2 3 5 7 11 13 17
128 83160 = 2^3 3^3 5 7 11
130 1658880 = 2^12 3^4 5
132 1244160 = 2^10 3^5 5
132 322560 = 2^10 3^2 5 7
132 691200 = 2^10 3^3 5^2
135 176400 = 2^4 3^2 5^2 7^2
135 3686400 = 2^14 3^2 5^2
135 518400 = 2^8 3^4 5^2
136 6881280 = 2^16 3 5 7
136 8847360 = 2^16 3^3 5
140 181440 = 2^6 3^4 5 7
140 1866240 = 2^9 3^6 5
140 3317760 = 2^13 3^4 5
140 648000 = 2^6 3^4 5^3
144 110880 = 2^5 3^2 5 7 11
144 1382400 = 2^11 3^3 5^2
144 138600 = 2^3 3^2 5^2 7 11
144 151200 = 2^5 3^3 5^2 7
144 180180 = 2^2 3^2 5 7 11 13
144 201600 = 2^7 3^2 5^2 7
144 241920 = 2^8 3^3 5 7
144 2488320 = 2^11 3^5 5
144 264600 = 2^3 3^3 5^2 7^2
144 272160 = 2^5 3^5 5 7
144 2799360 = 2^8 3^7 5
144 295680 = 2^8 3 5 7 11
144 645120 = 2^11 3^2 5 7
144 7372800 = 2^15 3^2 5^2
144 777600 = 2^7 3^5 5^2
144 864000 = 2^8 3^3 5^3
144 972000 = 2^5 3^5 5^3
147 1166400 = 2^6 3^6 5^2
150 1036800 = 2^9 3^4 5^2
150 1620000 = 2^5 3^4 5^4
150 226800 = 2^4 3^4 5^2 7
150 6635520 = 2^14 3^4 5
154 3732480 = 2^10 3^6 5
156 1290240 = 2^12 3^2 5 7
156 2764800 = 2^12 3^3 5^2
156 4976640 = 2^12 3^5 5
160 1296000 = 2^7 3^4 5^3
160 166320 = 2^4 3^3 5 7 11
160 1728000 = 2^9 3^3 5^3
160 240240 = 2^4 3 5 7 11 13
160 362880 = 2^7 3^4 5 7
160 378000 = 2^4 3^3 5^3 7
160 483840 = 2^9 3^3 5 7
160 5598720 = 2^9 3^7 5
160 591360 = 2^9 3 5 7 11
162 1555200 = 2^8 3^5 5^2
162 352800 = 2^5 3^2 5^2 7^2
162 403200 = 2^8 3^2 5^2 7
162 485100 = 2^2 3^2 5^2 7^2 11
162 8398080 = 2^8 3^8 5
165 2073600 = 2^10 3^4 5^2
168 1944000 = 2^6 3^5 5^3
168 221760 = 2^6 3^2 5 7 11
168 2332800 = 2^7 3^6 5^2
168 2580480 = 2^13 3^2 5 7
168 302400 = 2^6 3^3 5^2 7
168 544320 = 2^6 3^5 5 7
168 5529600 = 2^13 3^3 5^2
168 7464960 = 2^11 3^6 5
168 9953280 = 2^13 3^5 5
175 3240000 = 2^6 3^4 5^4
176 1182720 = 2^10 3 5 7 11
176 3456000 = 2^10 3^3 5^3
176 967680 = 2^10 3^3 5 7
180 2592000 = 2^8 3^4 5^3
180 277200 = 2^4 3^2 5^2 7 11
180 3110400 = 2^9 3^5 5^2
180 4147200 = 2^11 3^4 5^2
180 453600 = 2^5 3^4 5^2 7
180 4860000 = 2^5 3^5 5^4
180 5160960 = 2^14 3^2 5 7
180 529200 = 2^4 3^3 5^2 7^2
180 725760 = 2^8 3^4 5 7
180 806400 = 2^9 3^2 5^2 7
189 4665600 = 2^8 3^6 5^2
189 705600 = 2^6 3^2 5^2 7^2
192 1021020 = 2^2 3 5 7 11 13 17
192 1088640 = 2^7 3^5 5 7
192 1323000 = 2^3 3^3 5^3 7^2
192 1935360 = 2^11 3^3 5 7
192 2365440 = 2^11 3 5 7 11
192 332640 = 2^5 3^3 5 7 11
192 360360 = 2^3 3^2 5 7 11 13
192 3888000 = 2^7 3^5 5^3
192 415800 = 2^3 3^3 5^2 7 11
192 443520 = 2^7 3^2 5 7 11
192 480480 = 2^5 3 5 7 11 13
192 604800 = 2^7 3^3 5^2 7
192 6912000 = 2^11 3^3 5^3
192 6998400 = 2^7 3^7 5^2
192 756000 = 2^5 3^3 5^3 7
195 8294400 = 2^12 3^4 5^2
196 1632960 = 2^6 3^6 5 7
196 5832000 = 2^6 3^6 5^3
198 1612800 = 2^10 3^2 5^2 7
198 6220800 = 2^10 3^5 5^2
200 1134000 = 2^4 3^4 5^3 7
200 1451520 = 2^9 3^4 5 7
200 498960 = 2^4 3^4 5 7 11
200 5184000 = 2^9 3^4 5^3
200 6480000 = 2^7 3^4 5^4
208 3870720 = 2^12 3^3 5 7
208 4730880 = 2^12 3 5 7 11
210 907200 = 2^6 3^4 5^2 7
210 9331200 = 2^9 3^6 5^2
210 9720000 = 2^6 3^5 5^4
216 1058400 = 2^5 3^3 5^2 7^2
216 1209600 = 2^8 3^3 5^2 7
216 1360800 = 2^5 3^5 5^2 7
216 1411200 = 2^7 3^2 5^2 7^2
216 2177280 = 2^8 3^5 5 7
216 3225600 = 2^11 3^2 5^2 7
216 554400 = 2^5 3^2 5^2 7 11
216 7776000 = 2^8 3^5 5^3
216 887040 = 2^8 3^2 5 7 11
216 900900 = 2^2 3^2 5^2 7 11 13
216 970200 = 2^3 3^2 5^2 7^2 11
220 2903040 = 2^10 3^4 5 7
224 1512000 = 2^6 3^3 5^3 7
224 3265920 = 2^7 3^6 5 7
224 665280 = 2^6 3^3 5 7 11
224 7741440 = 2^13 3^3 5 7
224 9461760 = 2^13 3 5 7 11
224 960960 = 2^6 3 5 7 11 13
225 1587600 = 2^4 3^4 5^2 7^2
234 6451200 = 2^12 3^2 5^2 7
240 1774080 = 2^9 3^2 5 7 11
240 1814400 = 2^7 3^4 5^2 7
240 2268000 = 2^5 3^4 5^3 7
240 2419200 = 2^9 3^3 5^2 7
240 2646000 = 2^4 3^3 5^3 7^2
240 4354560 = 2^9 3^5 5 7
240 5806080 = 2^11 3^4 5 7
240 720720 = 2^4 3^2 5 7 11 13
240 831600 = 2^4 3^3 5^2 7 11
240 997920 = 2^5 3^4 5 7 11
243 2822400 = 2^8 3^2 5^2 7^2
243 5336100 = 2^2 3^2 5^2 7^2 11^2
250 5670000 = 2^4 3^4 5^4 7
252 1108800 = 2^6 3^2 5^2 7 11
252 2116800 = 2^6 3^3 5^2 7^2
252 2721600 = 2^6 3^5 5^2 7
252 6531840 = 2^8 3^6 5 7
256 1081080 = 2^3 3^3 5 7 11 13
256 1330560 = 2^7 3^3 5 7 11
256 1921920 = 2^7 3 5 7 11 13
256 2042040 = 2^3 3 5 7 11 13 17
256 2079000 = 2^3 3^3 5^3 7 11
256 3024000 = 2^7 3^3 5^3 7
256 9261000 = 2^3 3^3 5^3 7^3
256 9797760 = 2^7 3^7 5 7
264 3548160 = 2^10 3^2 5 7 11
264 4838400 = 2^10 3^3 5^2 7
264 8709120 = 2^10 3^5 5 7
270 1940400 = 2^4 3^2 5^2 7^2 11
270 3175200 = 2^5 3^4 5^2 7^2
270 3628800 = 2^8 3^4 5^2 7
270 5644800 = 2^9 3^2 5^2 7^2
280 1995840 = 2^6 3^4 5 7 11
280 4536000 = 2^6 3^4 5^3 7
288 1441440 = 2^5 3^2 5 7 11 13
288 1663200 = 2^5 3^3 5^2 7 11
288 1801800 = 2^3 3^2 5^2 7 11 13
288 2217600 = 2^7 3^2 5^2 7 11
288 2661120 = 2^8 3^3 5 7 11
288 2910600 = 2^3 3^3 5^2 7^2 11
288 2993760 = 2^5 3^5 5 7 11
288 3063060 = 2^2 3^2 5 7 11 13 17
288 3843840 = 2^8 3 5 7 11 13
288 4233600 = 2^7 3^3 5^2 7^2
288 5292000 = 2^5 3^3 5^3 7^2
288 5443200 = 2^7 3^5 5^2 7
288 6048000 = 2^8 3^3 5^3 7
288 6804000 = 2^5 3^5 5^3 7
288 7096320 = 2^11 3^2 5 7 11
288 9676800 = 2^11 3^3 5^2 7
294 8164800 = 2^6 3^6 5^2 7
300 2494800 = 2^4 3^4 5^2 7 11
300 7257600 = 2^9 3^4 5^2 7
300 7938000 = 2^4 3^4 5^3 7^2
315 6350400 = 2^6 3^4 5^2 7^2
320 2162160 = 2^4 3^3 5 7 11 13
320 3991680 = 2^7 3^4 5 7 11
320 4084080 = 2^4 3 5 7 11 13 17
320 4158000 = 2^4 3^3 5^3 7 11
320 5322240 = 2^9 3^3 5 7 11
320 7687680 = 2^9 3 5 7 11 13
320 9072000 = 2^7 3^4 5^3 7
324 3880800 = 2^5 3^2 5^2 7^2 11
324 4435200 = 2^8 3^2 5^2 7 11
324 6306300 = 2^2 3^2 5^2 7^2 11 13
324 8467200 = 2^8 3^3 5^2 7^2
324 9525600 = 2^5 3^5 5^2 7^2
336 2882880 = 2^6 3^2 5 7 11 13
336 3326400 = 2^6 3^3 5^2 7 11
336 5987520 = 2^6 3^5 5 7 11
360 3603600 = 2^4 3^2 5^2 7 11 13
360 4989600 = 2^5 3^4 5^2 7 11
360 5821200 = 2^4 3^3 5^2 7^2 11
360 7983360 = 2^8 3^4 5 7 11
360 8870400 = 2^9 3^2 5^2 7 11
378 7761600 = 2^6 3^2 5^2 7^2 11
384 4324320 = 2^5 3^3 5 7 11 13
384 5405400 = 2^3 3^3 5^2 7 11 13
384 5765760 = 2^7 3^2 5 7 11 13
384 6126120 = 2^3 3^2 5 7 11 13 17
384 6652800 = 2^7 3^3 5^2 7 11
384 8168160 = 2^5 3 5 7 11 13 17
384 8316000 = 2^5 3^3 5^3 7 11
400 6486480 = 2^4 3^4 5 7 11 13
420 9979200 = 2^6 3^4 5^2 7 11
432 7207200 = 2^5 3^2 5^2 7 11 13
448 8648640 = 2^6 3^3 5 7 11 13
d(n) n factored
====================================
int main()
{
system("date");
for(int e2 = 0; e2 <= 23; e2++){
for(int e3 = 0; e3 <= e2; e3++){
for(int e5 = 0; e5 <= e3; e5++){
for(int e7 = 0; e7 <= e5; e7++){
for(int e11 = 0; e11 <= e7; e11++){
for(int e13 = 0; e13 <= e11; e13++){
for(int e17 = 0; e17 <= e13; e17++){
mpz_class n = to_power(2,e2);
n *= to_power(3,e3);
n *= to_power(5,e5);
n *= to_power(7,e7);
n *= to_power(11,e11);
n *= to_power(13,e13);
n *= to_power(17,e17);
if( n < 10000000)
{
cout << setw(10) << mp_Divisor_Count(n) << " ";
cout << n << " = " << mp_Factored(n) << endl;
}
}}}}}}}
system("date");
return 0;
}
=======================================
Best Answer
Let $d(n)$ be the number of divisors for the natural number, $n$.
We begin by writing the number as a product of prime factors: $n = p^aq^br^c...$ then the number of divisors, $d(n) = (a+1)(b+1)(c+1)...$
To prove this, we first consider numbers of the form, $n = p^a$. The divisors are $1, p, p^2, ..., p^a$; that is, $d(p^a)=a+1$.
Now consider $n = p^aq^b$. The divisors would be:
$1, p, p^2, ..., p^a,$
$q, pq, p^2q, ..., p^aq,$
$q^2, pq^2, p^2q^2, ..., p^aq^2,$
$..., ..., ..., ..., ...,$
$q^b, pq^b, p^2q^b, ..., p^aq^b $
Hence we prove that the function, $d(n)$, is multiplicative, and in this particular case, $d(p^aq^b)=(a+1)(b+1)$. It should be clear how this can be extended for any natural number which is written as a product of prime factors.
http://mathschallenge.net/library/number/number_of_divisors