找到第一个阶乘可以被 x 整除的数？

Question

我是汇编编码的新手，如果有任何愚蠢的错误请指正......

Given a number x, your task is to find first natural number i whose factorial is divisible by x.

The number x will be stored in register %rax using the mov instruction.

The final result should be stored in register %rdi.

Assume x is chosen such that overflow does not occur.

我的尝试：

factorial:  

    pushq %rbp
    movq %rsp, %rbp 
    cmpq , %rdi   
    je if           
    jmp else

if:
                 
    movq , %rax
    jmp factend

else:
             
    pushq %rdi      
    subq ,%rdi    

    call factorial  
    popq %rdi       
    mulq %rdi      

    jmp factend      

factend:

    movq %rbp, %rsp
    popq %rbp
    ret

Answer 1

让我们来解决这个问题：

Given a number x, your task is to find first natural number i whose factorial is divisible by x.

即找到 n 使得 n! % x == 0.

如果将 n! 和 x 拆分为它们的质因数（例如“60 = 2*2*3*5”），您知道当所有质因数时余数将为零在 x 中也是在 n! 中的质因数；这意味着 n 必须等于或大于 x.

的最大质因数

在最坏的情况下，如果 x 是质数（只有一个质因数），则 n 必须等于 x。例如，如果 x 是 61，那么 n 将是 61。这很重要，因为 n! 很快变大并且会溢出（例如 61! 不适合 64位）。

还好；如果 n 大于 2； n! 等同于 (n-1)! * n； ((n-1)! * n) % x 与 ((n-1)! % x) * n) % x.

相同

换句话说；为了让它工作（避免溢出）你可以做这样的事情（不用每次计算 n! 本身）：

do {
  i = i + 1;
  remainder = remainder * i;
  remainder = remainder % x;
while(remainder != 0);

现在...

Assume x is chosen such that overflow does not occur.

这到底是什么意思？

如果索取代码的人假设您会使用我描述的算法；那么这可能意味着 x 将小于 1 << 64 的平方根）；因此，如果您使用 "more likely to overflow algorithm"（任何计算 n! 值的算法），您将出现溢出，因此您必须使用我的算法（或找到更好的算法）。

无论如何；递归不好而且没有必要。

找到第一个阶乘可以被 x 整除的数？

Find the first number whose factorial is divisible by x?

assembly

x86

x86-64

factorial