F #. Завершено из-за тайм-аута при решении проблемы Project Euler # 3 - PullRequest
Новая
       45

F #. Завершено из-за тайм-аута при решении проблемы Project Euler # 3

2 голосов
/ 05 марта 2019

Я говорил об этой проблеме: 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 .Что я могу сделать?

Ответы [ 2 ]

1 голос
/ 06 марта 2019

Есть решение: 

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

Спасибо Будет Несс и Ричи .

0 голосов
/ 06 марта 2019

Нет необходимости писать супер сложный код для этой задачи.Простой алгоритм перечисления простых факторов числа сделает свое дело.Мой код создает 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
...