مشكلة مشروع Euler 27 في F #

Question

لقد كنت أحاول العمل في طريقي المشكلة 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)

أي نصائح حول كيفية أ) الحصول على هذه الخوارزمية في الواقع إرجاع الإجابة الصحيحة (أعتقد أنني على الأقل اتخاذ نهج عملي) و B تحسين الأداء، لأنه يتجاوز بوضوح "قاعدة دقيقة واحدة" المحددة في المشروع أسئلة وأجوبة. أنا قليلا من مبتدئ البرمجة الوظيفية، لذلك أي نصيحة حول كيفية النظر في المشكلة في حل أكثر وظيفية في الاعتبار أيضا موضع تقدير.

Answer 1

ملاحظاتين:

1. قد تستفيد من حقيقة أن b يجب أن يكون prime.. وبعد هذا يتبع من حقيقة أن المشكلة تطلب أطول تسلسل من الأعداد الأولية n = 0, 1, 2, ... وبالتالي، formula(0) يجب أن يكون رئيسا للبدء، ولكن formula(0) = b, لذلك، يجب أن يكون ب رئيسا.

2. أنا لست مبرمج F #، ولكن يبدو لي أن الكود لا يحاول N = 0 على الإطلاق. وبعد هذا، بالطبع، لا تفي بمتطلبات المشكلة n يجب أن تبدأ من 0, وبالتالي هناك فرص تهمل يمكن أن يتم إنتاج إجابة صحيحة.

Answer 2

يمينا، بعد الكثير من التدقيق إلى أن جميع وظائف المساعد كانت تفعل ما يجب عليهم، فقد وصلت أخيرا إلى حل عمل (وفعال بشكل معقول).

أولا، is_prime. كانت الوظيفة خاطئة تماما (بفضل Dimitre Novatchev لجعلني ننظر إلى ذلك). لست متأكدا تماما كيف وصلت إلى الوظيفة التي نشرتها في السؤال الأصلي، لكنني تفترض أنها تعمل منذ أن كنت قد استخدمتها في المشاكل السابقة. (على الأرجح، كنت قد تعثرت عليها فقط وكسرها منذ ذلك الحين.) على أي حال، النسخة العاملة من هذه الوظيفة (والتي تعود بشكل كبير كاذبة لجميع الأعداد الصحيحة أقل من 2) هل هذا:

/// 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

كان المفتاح هنا لزيادة السرعة لتوليد مجموعة الأعداد الأولية فقط بين 1 و 1000 لقيم ب (باستخدام الأعداد الأولية وظيفة، تنفيذ بلدي من غربال طريقة eratosthenes). لقد نجحت أيضا في جعل هذا الرمز موجز أكثر قليلا من خلال القضاء على SEQ.Map غير الضروري.

لذلك، أنا سعيد للغاية بالحل الذي لدي الآن (يستغرق الأمر بموجب ما بعد ثانية)، على الرغم من أن أي اقتراحات أخرى ستظل موضع ترحيب ...

Answer 3

يمكنك تسريع وظيفة "is_prime" الخاصة بك باستخدام خوارزمية احتمالية. واحدة من أسهل الخوارزميات السريعة لهذا هو ميلر رابين خوارزمية.

Answer 4

للتخلص من نصف حساباتك، يمكنك أيضا جعل مجموعة من الممكنة تحتوي فقط على أرقام فردية فقط

Answer 5

حل الثعبان Superfast 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()