0

入力された数値 10^num の 2 つの最大余素因数を見つけるコードを作成する必要があります。

今、私は書いた：

def coprimes(num):
    for x in range (2, num):
        for y in range (2, num):
            while (gcd(x,y) == 1) & (x != y):
                if (x*y==num):
                    return (x,y)

これは、forloops のために明らかに非常に遅いプログラムです。端末に入力するたびに、応答が遅すぎます。これが正しいかどうかもわかりません。この方法を改善する方法について何か提案はありますか?

このメソッドの回答例は次のとおりです。

>>> coprimes(10)
(9765625, 1024)
4

1 に答える 1

2

あなたがしたい

return 2**num, 5**num

質問の定義が不明確であることに注意して2**num, 5**numください1, 10**num。ただし、これらの要因のペアは他のどの要因よりも高くなっています。

この答えにたどり着くには、因数の最大 1 つが 2 で割り切れ、最大 1 つが 5 で割り切れることに注意してください。一方の因数が 2 と 5 の両方で割り切れる場合、もう一方は 1 でなければなりません。任意の整数は 1 と互いに素です。1 つの因数が 2 で割り切れ、もう 1 つの因数が 5 で割り切れる場合、2 と 5 の最大べき乗を選択します。(どちらの数も 2 または 5 で割らないオプションでは、より低い係数が生成されます。)

于 2013-09-29T21:08:30.430 に答える