1

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

4

5 回答 5

7

两个备注：

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

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

于 2009-02-24T14:42:19.560 回答
3

是的，经过大量检查所有辅助函数都在做他们应该做的事情之后，我终于找到了一个可行的（并且相当有效的）解决方案。

首先，is_prime函数是完全错误的（感谢 Dimitre Novatchev 让我看一下）。我不太确定我是如何得出我在原始问题中发布的函数的，但我认为它是有效的，因为我在以前的问题中使用过它。（很可能，我刚刚对其进行了调整并打破了它。）无论如何，这个函数的工作版本（对于所有小于 2 的整数至关重要地返回 false）是这样的：

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

主要功能更改为以下内容：

/// 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 set_b = primes (int64 (n - 1)) |> List.to_array |> Array.map int
    let set_a = [|-(n - 1) .. n - 1|]
    let set_n = Seq.init_infinite (fun i -> i)
    set_b |> Array.map (fun b -> (set_a |> Array.map (fun a ->
        let formula n = n * n + a * n + b
        let num_conseq_primes = set_n |> Seq.find (fun n -> not (is_prime_mem (formula n)))
        (a * b, num_conseq_primes))
    |> Array.max_by snd)) |> Array.max_by snd |> fst

这里提高速度的关键是只为b的值生成 1 到 1000 之间的素数集（使用素数函数，我实现的埃拉托色尼筛法）。通过消除不必要的 Seq.map，我还设法使这段代码更加简洁。

所以，我对我现在拥有的解决方案非常满意（它只需要不到一秒钟的时间），当然任何进一步的建议仍然是受欢迎的......

于 2009-02-24T16:39:29.107 回答
1

您可以使用概率算法加速您的“is_prime”函数。最简单的快速算法之一是Miller-Rabin算法。

于 2009-02-24T14:16:30.700 回答
-1

为了摆脱一半的计算，您还可以使可能的数组只包含奇数

于 2009-05-29T15:18:41.120 回答
-3

我的超快python解决方案：P

flag = [0]*204
primes = []

def ifc(n): return flag[n>>6]&(1<<((n>>1)&31))

def isc(n): flag[n>>6]|=(1<<((n>>1)&31))

def sieve():
    for i in xrange(3, 114, 2):
        if ifc(i) == 0:
            for j in xrange(i*i, 12996, i<<1): isc(j)

def store():
    primes.append(2)
    for i in xrange(3, 1000, 2):
        if ifc(i) == 0: primes.append(i)

def isprime(n):
    if n < 2: return 0
    if n == 2: return 1
    if n & 1 == 0: return 0
    if ifc(n) == 0: return 1
    return 0    

def main():
    sieve()
    store()
    mmax, ret = 0, 0
    for b in primes:
        for a in xrange(-999, 1000, 2):
            n = 1
            while isprime(n*n + a*n + b): n += 1
            if n > mmax: mmax, ret = n, a * b
    print ret

main()
于 2010-12-13T14:49:07.410 回答