algorithm - 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

• 输入:9999999999999 输出: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。