找到第一个因式可被x整除的数字？

Question

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

给定一个数字x，您的任务是找到第一个自然因数i，其阶乘数可被x整除。

• 数字x将使用mov指令存储在寄存器％rax中。

• 最终结果应存储在寄存器％rdi中。

• 假设x被选择为不会发生溢出。

我的尝试：

factorial:  

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

if:

    movq $1, %rax
    jmp factend

else:

    pushq %rdi      
    subq $1,%rdi    

    call factorial  
    popq %rdi       
    mulq %rdi      

    jmp factend      

factend:

    movq %rbp, %rsp
    popq %rbp
    ret

Answer 1

让我们研究这个问题：

给定一个数字x，您的任务是找到第一个自然因数i，其阶乘数可被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);

现在...

假设选择x，以免发生溢出。

这实际上是什么意思？

[如果询问代码的人认为您正在使用我描述的算法；那么它可能意味着x小于1 << 64的平方根）；因此，如果您使用“更可能溢出算法”（任何会计算n!值的算法），那么您将产生溢出，因此必须使用我的算法（或找到更好的算法）。

无论如何；递归是不好的，也是不必要的。