F#项目欧拉问题27

Question

我一直试图通过Euler项目的问题27来解决这个问题,但是这个问题似乎让我很难过.首先,代码运行时间太长了(可能在我的机器上运行几分钟,但更重要的是,它返回了错误的答案,虽然在查看了一段时间之后我真的无法发现算法有任何问题.

这是我目前的解决方案代码.

/// Checks number for primality.
let is_prime n = 
    [|1 .. 2 .. sqrt_int n|] |> Array.for_all (fun x -> n % x <> 0)

/// Memoizes a function.
let memoize f = 
    let cache = Dictionary<_, _>()
    fun x -> 
        let found, res = cache.TryGetValue(x)
        if found then
            res
        else
            let res = f x
            cache.[x] <- res
            res

/// Problem 27
/// Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
let problem27 n =
    let is_prime_mem = memoize is_prime
    let range = [|-(n - 1) .. n - 1|]
    let natural_nums = Seq.init_infinite (fun i -> i)
    range |> Array.map (fun a -> (range |> Array.map (fun b ->
        let formula n = n * n + a * n + b
        let num_conseq_primes = natural_nums |> Seq.map (fun n -> (n, formula n))
                                |> Seq.find (fun (n, f) -> not (is_prime_mem f)) |> fst
        (a * b, num_conseq_primes)) |> Array.max_by snd)) |> Array.max_by snd |> fst

printn_any (problem27 1000)

有关如何a)使这个算法实际返回正确答案的任何提示(我认为我至少采取了可行的方法)和b)提高了性能,因为它明显超出了项目中规定的"一分钟规则"欧拉常见问题.我是函数式编程的新手,所以关于如何考虑更多功能性解决方案的问题的任何建议也将受到赞赏.

Answer 1

两个评论:

1. 你可以利用b必须是素数的事实.这是因为问题要求n = 0, 1, 2, ... So 的最长素数序列formula(0)必须是素数,但是formula(0) = b,因此,b必须是素数.

2. 我不是F#程序员,但在我看来,代码根本不会尝试n = 0.当然,这不符合n必须从中开始的问题要求0,因此可以忽略机会产生正确的答案.