math - 除数数

Question

如何在不遍历 n 的所有除数的情况下找到一个数字“n”的除数数，这些除数也可以被另一个数字“k”整除？我尝试了以下方法：

将 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是 的一个除数n可以被 整除k，那么d/k是 的一个除数n/k。反之，如果e是 的除数n/k，则e*k是 的除数n可被 整除k。

你的代码

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将不是一种保存加密算法。