math - 除数の数

Question

nのすべての約数をループせずに、別の数「k」でも割り切れる数「n」の約数を見つける方法は? 私は次のことを試しました：

n のすべての素因数の累乗を連想配列 A に格納し、k についても同様に行い、すべての素因数の累乗を配列 B に格納しました。

    ans = 1
    for a in A:    // Here a is the prime factor and A[a] gives its power
        ans *= if( a is present in B ) ? 1 : A[a] + 1
    print ans

注：宿題ではありません。

Answer 1

nで割り切れるの約数を求めるにはk:

• kが の約数でない場合n、数値は 0 です。
• それ以外の場合は、 の約数ですn/k。

が で割り切れるdの約数である場合、は の約数です。逆に、 が の約数である場合、はで割り切れるの約数です。nkd/kn/ken/ke*knk

あなたのコード

ans = 1
for a in A:    // Here a is the prime factor and A[a] gives its power
    ans *= if( a is present in B ) ? 1 : A[a] + 1
print ans

nと互いに素である の約数を計算しkます。

Answer 2

除数が素数の場合、すべての除数をループする以外に方法はありません。それ以外の場合、 RSAは保存暗号アルゴリズムではありません。