|
|
問題
約数の個数がC個になる最小の数Nを求める。
例
約数の個数が100個になる最小の数が45360である。
約数の個数が200個になる最小の数は498960である。
考察
C=a*b*c*…として、n=p^(a-1)*q^(b-1)*r^(c-1)* …
個数Cを約数の積に分解する。並びは大きい順とする。
例 48の場合
48=24*2=16*3=12*4=12*2*2=8*6=8*3*2=6*4*2=4*4*3=4*3*2*2=3*2*2*2*2
次に、素数を小さい順に割り当てて、約数をC個もつ数を生成する。
12*2*2の場合、2^11*3^1*5^1
（終り）
個数Cが奇数の場合、Nは平方数である。
OPTION ARITHMETIC RATIONAL !多桁の整数
DATA 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 !素数
DIM P(20)
MAT READ P
FOR C=1 TO 1000 !個数
LET N=2^(C-1) !仮の最小
CALL try(1,P,1,C, N)
PRINT STR$(C);":"; N
NEXT C
END
EXTERNAL SUB try(i,P(),S,F, N) !約数の積に分解する 例 12の場合、12=6*2=4*3=3*2*2
OPTION ARITHMETIC RATIONAL !多桁の整数
FOR D=1 TO INT(F/2) !約数の候補
IF MOD(F,D)=0 THEN !大きい順に F/1,F/2,F/3,…,3,2
LET FD=F/D
LET W=S*P(i)^(FD-1) !6*2のとき、2^5*3^1とする
IF W<N THEN !W≧Nなら、これ以降は可能性はない
IF D=1 THEN !分解が完了なら
LET N=W !最小のもの
ELSE
CALL try(i+1,P,W,D, N) !次へ
END IF
END IF
END IF
NEXT D
END SUB
実行結果
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 : 268435456
30 : 720
31 : 1073741824
32 : 840
33 : 9216
34 : 196608
35 : 5184
36 : 1260
37 : 68719476736
38 : 786432
39 : 36864
40 : 1680
41 : 1099511627776
42 : 2880
43 : 4398046511104
44 : 15360
45 : 3600
46 : 12582912
47 : 70368744177664
48 : 2520
49 : 46656
50 : 6480
|
|