質問の箱と球の問題をPythonで解いてみた。

 質問の箱と球の問題をPythonで解いてみました。(^_^;
 やっぱり、箱と球の問題というより、「約数の個数」の問題といった方がいいかも知れません。(^_^;

 1から100までの番号が書かれた箱がある。箱には球が5個ずつ入っている。次の操作で球を取り出す。
操作 1:2の倍数が書かれた箱から1つ取り出す
操作 2:3の倍数が書かれた箱から1つ取り出す
操作 3:4の倍数が書かれた箱から1つ取り出す
 …
操作99:100の倍数が書かれた箱から1つ取り出す
 問題:最後の操作のあと、球が3個入っている箱は、いくつありますか?

 ちなみに、数学的には、1〜100までのうち、1を除く約数が2つのもの、すなわち、約数の個数が3つのものになっています。それで、結局、素数の平方数を見つければいいことになるようです。(^_^;
 2×3×5=30<100<2×3×5×7=210なので、題意の自然数Mは、高々3つの素数a,b,cとそれぞれの指数x,y,zを使って、次のよう書ける。
 M=a^x \times b^y \times c^z
 このとき、その約数の個数Nは、
 N=(x+1)(y+1)(z+1)
となります。題意から、約数の個数が3つなので、
 (x+1)(y+1)(z+1)=3
 これを満たす整数解は、x≧y≧zとすると、
 (x,y,z)=(2,0,0)
 よって、題意の自然数Mは、次式のようになって素数の平方数となることがわかります。
 M=a^2 \times b^0 \times c^0=a^2

● BallsInBoxes1.py

# coding: UTF-8
# BallsInBoxes1.py

from time import time

def main():
    tm=time()  # Timer Start

    # 箱をbox[1]〜box[100]まで用意。box[0]はダミー
    box = [5]*101; box[0] = 0
    for i in range(2,101):
        for j in range(1,101):
            if j%i==0: box[j]-=1;
##    print(box)
    hit = []
    for i in range(101):
        if box[i]==3:
            hit.append(i)

    print(hit)
    print(u"∴%d"%len(hit))
    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

●実行結果

[4, 9, 25, 49]
∴4
Runtime : 0.002 [sec]

※参考URL
約数 - Wikipedia
約数の個数の求め方!素因数分解すれば一発で求まる!
受験算数の「約数の個数」の問題をPythonで解いてみた。
受験算数の「約数の個数」の問題をPythonで解いてみた。(2)