当时创造的中间值应我的商店？

Question

我努力学习F#所以我拜访 欧拉项目 我目前在工作 问题3.

总理因素的13195 5,7, 13和29。

什么是最大总理 因子的数量600851475143?

有些事情要考虑：

1. 我的第一优先是学习功能良好的习惯。
2. 我的第二优先是我想要的快速和有效的。

在下列代码，我已经标注的部分这一问题是有关.

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

Answer 1

编程功能变得更容易和更多的自动与实践，所以别担心如果你没有获得绝对正确的第一次尝试。

有鉴于此，让我们把你的样品代号：

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 版本，只是怪异的，不要使用它。我喜欢你的版本明确我们的结合。

另一种方式写这将是：

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

它的 "确定" 偶尔有用它写这样，但仍遇到一点都不奇怪。大部分时间，我们使用 |> 以咖喱值 没有 需要我们的变量名称(在"pointfree"风格)。试图预测如何功能将使用，并且如果可能的话，重新编写这样你可以用它与管道操作者没有明确宣布变量。例如：

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

没有更多的名args:)

---

Ok，现在我们已经说出来的方式，让我们来看看你 isPrime 功能：

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

你可能听说过使用递归，而不是循环的，这一点是正确的。但是，只要有可能，你应该抽象离递归的褶皱，地图，或更高阶的职能。两个原因：

1. 它的一个小更具可读性，

2. 不正确地写入递归的结果将在一堆溢出。例如，您功不是尾递归的，所以它就会炸毁大值 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#在速度方面，或者这将是"快不够"。如果你找到你的代码需要很长的时间来执行，这可能意味着你正在使用错误的数据结构或一个糟糕算法。对于一个具体的例子，读取意见 关于这个问题.

因此，代码我写的是"优雅"在这个意义上，它简明扼要，提供了正确的结果，并不依赖于任何欺骗。不幸的是，它没有速度非常快。为开始：

• 它使用审判分，以创建一系列的素，当筛埃拉托塞尼将快很多。[编辑：我写了一些幼稚的版本的这个筛其没有工作数量大于Int32。MaxValue，所以我已经删除了代码。]

• 阅读维基百科的文章 总理计数功能, 它会给你指在计算第一 n 质数，以及估计的上限和下限的 nth 总理。

[编辑：I包括了一些码有点幼稚的执行情况的筛埃拉托塞尼.它仅适用于输入低于int32。MaxValue，所以它可能不适合于项目的欧拉。]

Answer 2

关于"良好的功能习惯"或相当良好的实践中，我看到三个小东西。使用率在你的顺序是有点难以读的不仅仅是过滤器。不必要的类型的注解中的一个类推断的语言，导致难重构和使代码更难于阅读。不要做得过分，并试图删除的每一种类型的注释，但如果你发现这很困难。最后做的一氧功能，只需要价值，以用作临时变量减少可读性。

尽的个人风格我喜欢更多的空间，并且仅使用tupled参数的数据时有意义被归在一起。

我会写您的原始代码这样。

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

let greatestPrimeFactor n =
    let nextPrime prime = 
        seq {prime + 1L .. System.Int64.MaxValue}
        |> Seq.filter isPrime
        |> Seq.skipWhile (fun v -> n % v <> 0L) 
        |> Seq.head

    let rec findNextPrimeFactor number prime =
        if number = 1L then 
            prime 
        else 
            let p = nextPrime(prime)
            findNextPrimeFactor (number / p) p

    findNextPrimeFactor n 2L

你更新代码的最佳方法。你必须使用不同的算法喜欢阴朱答案走得更快。我写了一个测试，以检查来看看是否F#让的"检查"尾递归功能和它一样。

Answer 3

的 变量 p实际上是一个名字结合，不是一个可变的。使用的名称结合不是一个坏的样式。它是更具可读性。懒惰的风格 nextPrime 是良好的，以及它实际上，总理试验每个数目只有一次，在整个程序。

我的解决方案

let problem3 = 
    let num = 600851475143L
    let rec findMax (n:int64) (i:int64) =
        if n=i || n<i then
            n
        elif n%i=0L then
            findMax (n/i) i
        else
            findMax n (i+1L)
    findMax num 2L

我基本上将数从2,3,4..并不考虑任总理的数字。因为如果我们将所有的2num，那么我们不能将它分通过的4，8，等等。

在这个号码，我的解决方案是快:

> greatestPrimeFactor 600851475143L;;
Real: 00:00:01.110, CPU: 00:00:00.702, GC gen0: 1, gen1: 1, gen2: 0
val it : int64 = 6857L
> 
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val problem3 : int64 = 6857L

Answer 4

我认为，代码的临时结合是明显的更易于阅读。这是很不寻常，以创建一个匿名的功能，然后立即将其应用于一个值为你做在其他情况。如果你真的想要避免使用一个临时价值，我认为大多数习惯用的方式做到这F#中将使用 (|>) 操作者管该价值为的匿名的功能，但我仍然认为，这是不完全的可读性。