代码之家 › 专栏 › 技术社区 › Poppy Field

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

primes f# algorithm

Poppy Field · 技术社区 · 7 年前

我说过这个问题: 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
输入: 999999999999999 输出: 909091号 运行时间: 00:00:00.1260673

但我还是因为超时而被终止 测试用例5 .我能做什么?

0 回复 | 直到 7 年前

Poppy Field 7 年前

有一个解决方案:

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()

谢谢 意志力 和 蓖麻毒素 是的。

dumetrulo 7 年前

没有必要为这个挑战编写超级复杂的代码。一个简单的算法来枚举一个数的素数因子就可以了。我的代码创建 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