約数の個数

 投稿者:山中和義  投稿日:2013年 8月16日(金)19時37分23秒
  問題
約数の個数が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

 

Re: 約数の個数

 投稿者:GAI  投稿日:2013年 8月17日(土)07時58分54秒
  > No.3110[元記事へ]

山中和義さんへのお返事です。

私的数学塾で投稿していた任意の約数の個数に対する最小数を見つけるプログラムを見せてもらいまして、こんな効率よい組み方が可能であると感心いたしました。
(思ったよりもスッキリと少ないステップで記述できるんですね。)
自分はまだプログラムを作るときの全体の構成方法や、細かい部分を実行させるためのテクニックが(どんな変数を導入して、なにを変化させていけばいいのかが見えてきません。)
圧倒的に不足しています。
掲載されたプログラムをじっくり分析させてもらって、その流れを辿っていきたいと思います。
是非外部副プログラムを使って、仕事の割り当てをしていくコツを身につけたいです。
丸一日かけても見えなかった線がこうして示されたことで、どこで迷っていたかが認識できるようになりました。
プログラムの掲載ありがとうございました。(一日でもはやく、山中さんのようになりたい!)
 

戻る