AtCoder 142のD問題についての振り返り

こんにちは、近頃数学ではなくPythonやAtCoderに浮気しています.
数学では近頃可換環論ばかりやっていたこともあり、髪の毛を赤に染めました.*1

最近、機械学習の勉強会が始まったため、Pythonを扱うことが多くなりました.Twitterで情報を集め、文法の練習としてAtCoderを扱うことにしました.*2
感想としては、AtCoderが楽しすぎるし、特にアルゴリズムを自力で考えて、もし速度が出なかったら自分で改良するたのしさが強いです.
自分の経験上、学ぶ際には優れている人を真似るというのが最善と思ってはいますが、自分の知識をフルに生かして、いかに効率的なアルゴリズムを考えるというよろこびを感じています.
プログラミングに関しては、CとC++のある程度の文法はわかる程度で、実際に何かを作ったということはありませんでした.そんななかでAtCoderでコンピュータだからこそ解けるような数学の問題を自らプログラミングして解くことは楽しいものでした.*3

今後、アルゴリズムを勉強していくつもりですが、自力で書いたAtCoder142D問題のコードを足跡として置いておくことにします.

atcoder.jp ↑問題はこれ
python5日目の自分が考えたコードゆえ読みづらいと思いますが、改善点などがあればTwitter(@mist0ne)にてお教え頂けると嬉しいです.

C,D = [int(e) for e in input().split()]

if C <= D:
    m = D
    n = C
else:
    m = C
    n = D

while  n != 0 :
    a = m%n
    m = n
    n = a

J = []

for i in range(1,int(m**0.5)+1):　#与えられた2整数の最大公約数を元に公約数を列挙している.
    if m % i == 0:
        J.append(i)
        if i != m//i:
            J.append(m//i)


J.sort()

N = int(len(J))
M = [1]
I = []

for i in range(1,N):　　　#公約数のうちどれとも互いに素であるもの、すなわち素数を探している.
    for p in range(1,int(J[i]**0.5)+1):
        if J[i]%p == 0:
            I.extend([J[i]])
            if int(len(I)) >=2:
                break
    if int(len(I)) == 1:
        M.extend([J[i]])
    I = []


M = int(len(M))

print(M)

工夫としては、はじめ最後方の31行目から35行目、breakを使わないと制限時間オーバーだった.まあbreakを使って書き換えたおかげで全部200ms以内で終わるようになったあたり、総当たりがどれだけ無駄があるのかが想像できる.
あと、初めからM=[1]と定義しているのは面倒ごとを避けるためである.
今後の目標はとりあえず、D問題を安定して解けるようにして、F問題まで安定して解きたいね.

*1:松村可換環論の表紙は赤色である.

*2:集めるというよりむしろ、某人工痴能さんに聞きまくってお世話になってます

*3:実際、大学以上でやるような数学は計算はほとんどしません.積分の計算なんてしないし、ひたすら証明してます.