问询质数幂乘积比较算法：判断无公共质数的质数幂乘积大小

当然存在这样的算法，核心思路是利用对数的单调性将乘法/幂运算转换为加法/乘法运算，避开直接计算超大数值的溢出问题。

算法原理 #

因为对数函数（如自然对数ln(x)、常用对数log10(x)）是严格单调递增的，所以对于两个正数A和B，A > B等价于ln(A) > ln(B)。

针对你的问题场景：

• 表达式A是若干不同质数的幂的乘积：A = p₁^e₁ * p₂^e₂ * ... * pₙ^eₙ
• 表达式B是另一组无公共质数的幂的乘积：B = q₁^f₁ * q₂^f₂ * ... * qₘ^fₘ

对两者取自然对数后可得：

ln(A) = e₁*ln(p₁) + e₂*ln(p₂) + ... + eₙ*ln(pₙ)
ln(B) = f₁*ln(q₁) + f₂*ln(q₂) + ... + fₘ*ln(qₘ)

只需比较这两个求和结果的大小，就能得到原表达式的大小关系。

具体步骤 #

1. 预计算质数的对数：针对两个表达式中出现的所有质数，计算其足够精度的对数（比如保留50位以上小数，应对2^64级别的超大指数）。
2. 计算对数总和：分别遍历两个表达式的质数-指数对，将每个质数的对数乘以对应指数，累加得到两个总和。
3. 比较总和：
   • 若ln(A) > ln(B)，则A > B
   • 若ln(A) < ln(B)，则A < B
   • 若两者相等（理论上因质数无交集、指数为整数，这种情况几乎不存在），则A = B

示例验证 #

以你给出的例子：(7^21)*(2^49) vs (5^26)*(3^31)

• 计算左边对数和：21*ln(7) + 49*ln(2) ≈ 21*1.94591 + 49*0.69315 ≈ 74.82846
• 计算右边对数和：26*ln(5) + 31*ln(3) ≈ 26*1.60944 + 31*1.09861 ≈ 75.90235
• 因为74.82846 < 75.90235，所以(7^21)*(2^49) < (5^26)*(3^31)，和实际数值计算结果一致。

超大指数的处理 #

对于2^64级别的指数，只需用支持大整数的类型存储（比如Python的int、C++的unsigned long long），再与高精度对数相乘即可。若遇到对数总和极其接近的情况，可使用任意精度数学库提升计算精度，确保误差小于两个总和的差值绝对值，避免误判。

内容的提问来源于stack exchange，提问作者Sergei