F＃。解决 Project 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.0520280
输入：987654321852输出：680202701运行时间：00:00:00.0564059
输入：13652478965478输出：2275413160913运行时间： 00:00:00.0593369
输入：99999999999999输出：909091运行时间：00:00:00.1260673

但是在测试用例 5 中，由于超时，我还是被终止了。我能做什么？

Answer 1

无需为此挑战编写超级复杂的代码。一个简单的算法来枚举一个数字的质因数就可以了。我的代码创建了一个 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

Answer 2

有解决办法：

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。

F＃。解决 Project Euler #3 问题时因超时而终止

F#. Terminated due to timeout when solving Project Euler #3 problem

algorithm

f#

primes

prime-factoring