我一直在努力解决 Project 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)提高性能,因为它显然超过了项目中规定的“一分钟规则”欧拉常见问题。我是函数式编程的新手,所以任何关于我如何考虑更实用的解决方案的问题的建议也将不胜感激。