math - 找到一个大阶乘数的除数之和？

Question

我试图想出一种有效的方法来列出一个大阶乘的所有除数。比方说1000！用蛮力是完全不可能的。有没有有效的方法？我需要处理它们，即找到它们的总和以应对编程挑战。

Answer 1

1. 找到每个数字 <= 1000 的素数分解。我会将其存储为素数 -> 幂的字典。例如，对于像 24 这样的单个数字，{2: 3, 3: 1}因为 24 是2**3 * 3**1。
2. 求 的素因数分解1000!。这是数字 <= 1000 的字典的组合，通过对每个键（素数）的所有值求和来组合。
3. 然后，您可以使用此页面上的公式 14，正如 @AakashM 已经说过的那样。

Answer 2

以下是有效解决方案的步骤：

1. 嗯！可以表示为：- n! = (a1^p1) (a2^p2)x...(ak^pk)。

   其中 ak 是小于 n 的素数除数，而 pk 是可以除 n! 的最高幂。

2. 通过筛子找到素数和最高幂可以很容易地找到：

   countofpower =  [n/a] + [n/a^2] + [n/a^3] +...... or   `  while (n)
   {
     n/ = a;
     ans += n
   }
   

3. 因素计数 =(ans1 +1)*(ans2 +1)*....(ansk +1)

4. 在计算这最后一步之后是总和：

   SUM = product of all (pow(ak,pk+1)-1)/(ak-1);
   ex = 4! 
   4! = 2^3 * 3^1;
   count of factors = (3+1)*(1+1) = 8 (1,2,3,4,6,8,12,24)
   sum = ( 1 + 2 + 4 + 8)*(1 + 3) = 60.