効率的に約数の個数を求めるアルゴリズムを考えているが、まだ四苦八苦している状態。つまり、1～500万までの整数について、それぞれの約数の数を一気に求めたい。
個々の整数なら、素因数分解して、因数の指数の積で約数の数が分かるのだが、1個1個やっているのでは、遅すぎて話にならない。
それよりも多少高速なプログラムは以下の通り。それでも数秒かかってしまう。
#define MAX 5000000
int c[MAX+10]; /* 約数の数を記録する */
void calc(void)
{
int i, j;
for (i = 1; i <= MAX; i++) c[i] = 1;
for (j = 2; j <= MAX; j++) {
for (i = j; i <= MAX; i+=j) c[i]++;
}
}
プログラム自体は約数の定義そのものなので、面白みがないけど、圧倒的に分かりやすい。
さて、約数の数について、規則性を見るために、500万までの整数のうち、約数の個数が 1, 2, 3, …100となる整数の個数をリストアップしてみた。
約数の数が１の整数は１だけ。約数の数が2の整数は素数、つまり500万までの整数のうち、素数となる整数は348513個もある。だが、約数の数が８の整数が一番多いことに不思議さを感じている。ほかにも面白いことが沢山潜んでいるようだ。
(1,1) (2,348513) (3,331) (4,978982) (5,15) (6,189382) (7,6) (8,1118592) (9,630) (10,34670) (11,2) (12,429792) (13,2) (14,8631) (15,213) (16,689491) (17,1) (18,38545) (19,1) (20,71017) (21,89) (22,675) (23,1) (24,362994) (25,13) (26,201) (27,386) (28,16023) (29,0) (30,11399) (31,0) (32,248237) (33,21) (34,20) (35,11) (36,61776) (37,0) (38,7) (39,11) (40,50345) (41,0) (42,2722) (43,0) (44,984) (45,209) (46,0) (47,0) (48,146533) (49,2) (50,703) (51,3) (52,243) (53,0) (54,3921) (55,4) (56,9754) (57,1) (58,0) (59,0) (60,15024) (61,0) (62,0) (63,70) (64,50410) (65,2) (66,208) (67,0) (68,11) (69,0) (70,292) (71,0) (72,31359) (73,0) (74,0) (75,33) (76,1) (77,2) (78,59) (79,0) (80,15341) (81,84) (82,0) (83,0) (84,2909) (85,0) (86,0) (87,0) (88,400) (89,0) (90,1291) (91,1) (92,0) (93,0) (94,0) (95,0) (96,27891) (97,0) (98,27) (99,10) (100,700)
約数の数が与えられて、もとの整数を高速に計算するプログラムも考えたい。
最後に、約数の数が1, 2, 3, … 100となる、それぞれの最小整数をリストアップしておく。（ご注意、あくまでも500万までの整数のうち。拡大していけば、0の部分はなくなる。）
(1,1) (2,2) (3,4) (4,6) (5,16) (6,12) (7,64) (8,24) (9,36) (10,48) (11,1024) (12,60) (13,4096) (14,192) (15,144) (16,120) (17,65536) (18,180) (19,262144) (20,240) (21,576) (22,3072) (23,4194304) (24,360) (25,1296) (26,12288) (27,900) (28,960) (29,0) (30,720) (31,0) (32,840) (33,9216) (34,196608) (35,5184) (36,1260) (37,0) (38,786432) (39,36864) (40,1680) (41,0) (42,2880) (43,0) (44,15360) (45,3600) (46,0) (47,0) (48,2520) (49,46656) (50,6480) (51,589824) (52,61440) (53,0) (54,6300) (55,82944) (56,6720) (57,2359296) (58,0) (59,0) (60,5040) (61,0) (62,0) (63,14400) (64,7560) (65,331776) (66,46080) (67,0) (68,983040) (69,0) (70,25920) (71,0) (72,10080) (73,0) (74,0) (75,32400) (76,3932160) (77,746496) (78,184320)
(79,0) (80,15120) (81,44100) (82,0) (83,0) (84,20160) (85,0) (86,0) (87,0) (88,107520) (89,0) (90,25200) (91,2985984) (92,0) (93,0) (94,0) (95,0) (96,27720) (97,0) (98,233280) (99,230400) (100,45360)
1以外は、すべて偶数のようだ。
指定された約数の数となる、最小整数を求める (Smallest number with exactly n divisors) プログラム。それも面白そう。
約数の数が素数の場合は簡単に分かるが、素数以外の場合はどうなっているんだろう。
