f# - 创建中介值时，我应该存储它吗？

我正在尝试学习F＃，所以我访问了Project Euler，目前正在研究Problem 3。


13195的主要因素是5、7
13和29。

什么是最大素数
数的倍数600851475143？


要考虑的一些事情：


我的首要任务是学习良好的功能习惯。
我的第二个优先事项是我希望它快速有效。


在以下代码中，我已标记了该问题所涉及的部分。

let isPrime(n:int64) =
    let rec check(i:int64) =
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L)

let greatestPrimeFactor(n:int64) =
    let nextPrime(prime:int64):int64 =
        seq { for i = prime + 1L to System.Int64.MaxValue do if isPrime(i) then yield i }
        |> Seq.skipWhile(fun v -> n % v <> 0L)
        |> Seq.hd
    let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))
            //*************
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p)
            //*************
    findNextPrimeFactor(n, 2L)

更新资料

基于一些反馈，我将代码重构为快10倍。

module Problem3

module private Internal =
    let execute(number:int64):int64 =
        let rec isPrime(value:int64, current:int64) =
            current > value / 2L or (value % current <> 0L && isPrime(value, current + 1L))
        let rec nextPrime(prime:int64):int64 =
            if number % prime = 0L && isPrime(prime, 2L) then prime else nextPrime(prime + 1L)
        let rec greatestPrimeFactor(current:int64, prime:int64):int64 =
            if current = 1L then prime else nextPrime(prime + 1L) |> fun p -> greatestPrimeFactor(current / p, p)
        greatestPrimeFactor(number, 2L)


let execute() = Internal.execute(600851475143L)

更新资料

我要感谢大家的建议。最新版本是我收到的所有建议的汇总。

module Problem3

module private Internal =
    let largestPrimeFactor number =
        let rec isPrime value current =
            current > value / 2L || (value % current <> 0L && isPrime value (current + 1L))
        let rec nextPrime value =
            if number % value = 0L && isPrime value 2L then value else nextPrime (value + 1L)
        let rec find current prime =
            match current / prime with
            | 1L -> prime
            | current -> nextPrime (prime + 1L) |> find current
        find number (nextPrime 2L)

let execute() = Internal.largestPrimeFactor 600851475143L

最佳答案

通过实践，函数式编程将变得更加容易和自动化，因此，如果您在第一次尝试中没有完全正确的话，请不要大汗淋漓。

考虑到这一点，让我们看一下示例代码：

let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))
            //*************
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p)
            //*************

您的no variable版本很奇怪，请勿使用。我喜欢带有显式let绑定的版本。

另一种写法是：

nextPrime(prime) |> fun p -> findNextPrimeFactor(number / p, p)

这样写是可以的，偶尔有用，但是仍然有点怪异。在大多数情况下，我们使用|>来咖喱值而无需命名变量（“无点”样式）。尝试预期函数的使用方式，并在可能的情况下重新编写函数，以便可以将其与管道运算符一起使用，而无需使用显式声明的变量。例如：

let rec findNextPrimeFactor number prime =
    match number / prime with
    | 1L -> prime
    | number' -> nextPrime(prime) |> findNextPrimeFactor number'

不再命名为args :)



好的，现在我们已经解决了这个问题，让我们来看一下您的isPrime函数：

let isPrime(n:int64) =
    let rec check(i:int64) =
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L)

您可能听说过使用递归而不是循环，这很对。但是，在任何可能的地方，您都应该使用折叠，地图或高阶函数来抽象递归。这有两个原因：


它更具可读性，并且
编写不正确的递归将导致堆栈溢出。例如，您的函数不是尾部递归，因此它会在n较大的值时爆炸。


我会这样重写isPrime：

let isPrime n = seq { 2L .. n / 2L } |> Seq.exists (fun i -> n % i = 0L) |> not

在大多数情况下，如果您可以抽象化显式循环，则只需对输入序列应用转换，直到获得结果：

let maxFactor n =
    seq { 2L .. n - 1L }                        // test inputs
    |> Seq.filter isPrime                       // primes
    |> Seq.filter (fun x -> n % x = 0L)         // factors
    |> Seq.max                                  // result

在此版本中，我们甚至没有中间变量。太酷了！




我的第二要务是我想要
快速高效。


大多数时候，F＃在速度方面将与C＃相当，或者“足够快”。如果发现代码执行时间很长，则可能意味着您使用了错误的数据结构或错误的算法。有关具体示例，请阅读注释on this question。

因此，我编写的代码简洁，可以给出正确的结果并且不依赖任何技巧，因此是“优雅的”。不幸的是，它不是很快。首先：


当Eratosthenes筛子要快得多时，它会使用试验除法来创建素数序列。 [编辑：我写了这个筛子的一个天真版本，对于大于Int32.MaxValue的数字不起作用，所以我删除了代码。
阅读Wikipedia关于prime counting function的文章，它将为您提供有关计算第一个n素数以及估算nth素数的上限和下限的指针。


[编辑：我提供了一些代码，其中包括一些简单的实现eratosthenes的方法。它仅适用于小于int32.MaxValue的输入，因此它可能不适合项目euler。