functional-programming - 找到最小 m > n 使得 m 和 n 不是互质的函数

Question

首先，我几乎是全新的函数式编程（和一般编程），所以如果这看起来像一个愚蠢的问题，我提前道歉。无论如何，我一直在做一些编程练习并且到目前为止做得很好，但是这个让我卡住了：

我需要创建一个函数 fn : int -> int，它对于 n > 0 找到最小的 m > n，使得 m 和 n不是相对素数。这是我到目前为止所做的：

(* returns true if p,q are relative primes, else false *)
fun relativePrimes (1,q) = true
    | relativePrimes (p,q) = if p <> 0 then relativePrimes(q mod p,p) else false;

我在

fun nextNotRelativePrime n = if relativePrimes (n,n+1) = false then n+1
    else if relativePrimes (n,n+2) = false then n+2 else n*2; (* and so on... *)

这里的问题是这个函数只适用于n <= 9。当然，我可以用更多的情况来扩展它，但它仍然不适用于所有n。

我需要一种方法将相对素数 (p,q) 中的 q（最多 n*2）的 n 增加 1，而每次调用函数时 p = n 保持不变。我不知道如何。

Answer 1

要在循环中实现搜索，您需要一个将循环索引作为附加参数的辅助函数。

至于数学问题，最好的解决方法如下：

找到 的最小素因子p，m然后让n = m + p。

要找到p你可以只使用试除法直到并包括 的平方根m。如果你没有找到一个因素，那么m就是素数p = m。

有更好的方法来分解m没有小的素因子的大因子，例如波拉德 rho 算法的布伦特变体。