Javascript 除数

Question

我知道如何找到给定整数(1 除外)的除数:

let smallest_divisor n = 
    let rec aux n i = 
        if i < (n / 2) then n
        else if (i mod n == 0) then n
        else aux n (i + 1)
    in aux n 2;;

但是我如何找到它的除数(除了它本身)？

Answer 1

一种方法是从 n/2 开始，而不是从 2 开始并通过 (i + 1) 向上工作通过(i - 1)向下工作。

另一种方法是根据 smallest_divisor 编写 biggest_divisor:

let biggest_divisor n = n / smallest_divisor n ;;

<小时/>

编辑添加:在平均情况下，第二种方法实际上更有效，因为小除数比大除数更接近于n/2。 (如果 2 不是除数，则下一个可能的最小除数是 3，这是您尝试的下一个除数；如果n/2 不是除数，则下一个最大的可能除数是n/3，这涉及到迭代n/6种可能性。)

在评论中，您写道，出于某种原因，您不希望 biggest_divisor 依赖于 smallest_divisor。就我个人而言，我认为这是一个错误；但如果您对此有强烈的感觉，那么您最好的选择可能是模仿 n/smallest_divisor n 方法，从 2 迭代，然后返回 n/i 当你找到除数时。

顺便说一句，您可以通过在 i * i > n 时立即中止而不是等到 i > n/2 来提高这两种方法的性能。这样你只需要尝试 √n 个 i 可能的值，而不是 n/2 i 可能的值>，在检测到 n 是素数之前。