F＃.解决项目Euler＃3问题时由于超时而终止

Question

我告诉我这个问题：https：//www.hackerrank.com/contests/projecteuler/challenges/euler003

我试图解决此问题如下：

open System

let isPrime n =
    match n with
    | _ when n > 3L && (n % 2L = 0L || n % 3L = 0L) -> false
    | _ ->
        let maxDiv = int64(System.Math.Sqrt(float n)) + 1L
        let rec f d i = 
            if d > maxDiv then 
                true
            else
                if n % d = 0L then 
                    false
                else
                    f (d + i) (6L - i)     
        f 5L 2L
let primeFactors n =
    let rec getFactor num proposed acc =
        match proposed with
        | _ when proposed = num -> proposed::acc
        | _ when num % proposed = 0L -> getFactor (num / proposed) proposed (proposed::acc)
        | _ when isPrime num -> num::acc
        | _ -> getFactor num (proposed + 1L) acc
    getFactor n 2L []

let pe3() =
    for i = 1 to Console.ReadLine()  |> int  do
        let num = Console.ReadLine() |> int64
        let start = DateTime.Now
        primeFactors num 
            |> List.max
            |> printfn "%i" 
        let elapsed = DateTime.Now - start
        printfn "elapsed: %A" elapsed
pe3()

我的测试结果：

• 输入： 10 输出： 5 经过的时间： 00：00：00.0562321

• 输入： 123456789 输出： 3803 弹出时间： 00：00：00.0979232

• 输入： 12345678999 输出： 1371742111 出现时间： 00：00：00.0.0520280

• 输入： 987654321852 输出： 680202701 出现时间： 00：00.00.0564059

• 输入： 13652478965478 输出： 2275413160913 过去的时间： 00：00：00.0593369

• 输入： 99999999999999 输出： 909091 出现时间： 00：00：00.1260673

，但无论如何我因测试案例5 的超时而被终止。我该怎么办？

Answer 1

有一个解决方案：

open System
let primeFactors n =
    let rec getFactor num proposed acc =
       match proposed with
       | _ when proposed*proposed > num -> num::acc
       | _ when num % proposed = 0L -> getFactor (num / proposed) proposed (proposed::acc)
       | _ -> getFactor num (proposed + 1L) acc
    getFactor n 2L []
let pe3() =
    for i = 1 to Console.ReadLine()  |> int  do
        printfn "%i" (primeFactors (Console.ReadLine() |> int64)).Head
pe3()

谢谢 Will ness 和 rici 。

Answer 2

无需为此挑战编写超级复杂的代码。一种简单的算法来列举数字的主要因素，这将是解决问题的。我的代码创建了主要因素的seq，然后找到最大因素，然后打印它。该代码的其余部分显示了从标准输入中读取行的线路处理的一种很好的功能方法。

module Auxiliaries =
    let isNull (x : 'a when 'a : not struct) =
        match box x with
        | null -> true
        | _ -> false
    let refAsOption x =
        if isNull x then None else Some x
    let readLinesFromTextReader r =
        let tryRdLn (r : System.IO.TextReader) =
            try refAsOption (r.ReadLine ()) with _ -> None
        let gen r =
            tryRdLn r |> Option.map (fun s -> (s, r))
        Seq.unfold gen r
module Contest =
    let factors num =
        let next n =
            if n = 2L then 3L
            elif n % 6L = 1L then n + 4L
            else n + 2L
        let rec loop nn ct lf =
            seq {
                if ct * ct > nn then
                    if nn > lf then yield nn
                elif nn % ct = 0L then
                    yield ct
                    yield! loop (nn / ct) ct ct
                else
                    yield! loop nn (next ct) lf
            }
        loop num 2L 0L
    let euler003 n = factors n |> Seq.max
    let () =
        Auxiliaries.readLinesFromTextReader stdin
        |> Seq.skip 1
        |> Seq.map (int64 >> euler003)
        |> Seq.iter stdout.WriteLine