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）プロジェクトで設定された「1分間のルール」を明らかに超えているため、パフォーマンスを改善しますオイラーFAQ. 私は関数型プログラミングの初心者なので、より機能的なソリューションを念頭に置いて問題をどのように検討するかについてのアドバイスもいただければ幸いです。

4

5 に答える 5

7

2つの意見：

  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)

main 関数は次のように変更されました。

/// 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 を削除することで、このコードを少し簡潔にすることもできました。

だから、私は今持っている解決策にかなり満足しています（1秒もかかりません）が、もちろん、それ以上の提案は大歓迎です...

于 2009-02-24T16:39:29.107 に答える
1

確率的アルゴリズムを使用して、「is_prime」関数を高速化できます。このための最も簡単なアルゴリズムの 1 つは、Miller-Rabinアルゴリズムです。

于 2009-02-24T14:16:30.700 に答える
-1

計算の半分を取り除くために、可能なaの配列に奇数のみを含めることもできます

于 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 に答える