Projekt Euler Problem 27 in F #

Question

Ich habe versucht, meinen Weg durch Problem 27 zu arbeiten Projekt Euler, aber dieses scheint mir stumping zu werden. Zum einen wird der Code nimmt vielleicht viel zu lange laufen zu lassen (ein paar Minuten, auf meiner Maschine, aber noch wichtiger ist, es ist die falsche Antwort Rückkehr obwohl ich wirklich nichts falsch mit dem Algorithmus nach einem Blick durch sie eine Zeit lang vor Ort können .

Hier ist mein aktueller Code für die Lösung.

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

Irgendwelche Tipps, wie a), um diesen Algorithmus zu bekommen tatsächlich die richtige Antwort Rückkehr (ich glaube, ich bin zumindest einen tragfähigen Ansatz) und b) die Leistung verbessern, da sie eindeutig die „one-Minuten-Regel“ gesetzt überschreiten out im Projekt Euler FAQ. Ich bin ein bisschen wie ein Neuling auf dem funktionale Programmierung, so dass jeder Rat, wie ich könnte das Problem mit einer funktionellen Lösung im Auge auch erkannt werden, würde in Betracht ziehen.

Answer 1

Zwei Bemerkungen:

1. Sie können die Vorteile der Tatsache, dass b Primzahl sein muss . Dies folgt aus der Tatsache, dass das Problem für die längste Sequenz von Primzahlen für n = 0, 1, 2, ... fragt Also, formula(0) muss Primzahl beginnen, aber formula(0) = b muss daher b prim sein.

2. Ich bin kein # -Programmierer F, aber es scheint mir, dass der Code nicht funktioniert versuchen, n = 0 bei allen . Dies ist natürlich, entspricht nicht der Anforderung des Problem, das von n beginnen 0 müssen, daher gibt es vernachlässigbare Chancen eine richtige Antwort erzeugt werden könnte.

Answer 2

Richtig, nach einer Menge der Überprüfung aller Hilfsfunktionen wurden zu tun, was sie sollten, habe ich erreicht schließlich eine Arbeits (und einigermaßen effizient) Lösung.

Zunächst wird die is_prime Funktion war völlig falsch (dank Dimitre Novatchev dafür, dass ich das betrachten). Ich bin mir nicht ganz sicher, wie ich in der Funktion kam ich in der ursprünglichen Frage gestellt, aber ich hatte angenommen, es funktioniert, da ich es in früheren Problemen benutzt hatte. (Wahrscheinlich hatte ich zwickte es einfach und gebrochen es da.) Wie dem auch sei, die Arbeitsversion dieser Funktion (die entscheidend false zurückgibt für alle ganzen Zahlen weniger als 2), ist dies:

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

Die Hauptfunktion wurde geändert auf die folgenden:

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

Der Schlüssel ist hier die Geschwindigkeit zu erhöhen war, nur die Menge der Primzahlen zwischen 1 und 1000 für die Werte von erzeugen b (unter Verwendung des Primzahlen Funktion, meine Umsetzung der Sieb von Eratosthenes Methode). Ich schaffte es auch durch den Wegfall der unnötige Seq.map etwas prägnanter dieser Code zu machen.

Also, ich bin ziemlich glücklich mit der Lösung, die ich jetzt habe (es dauert knapp eine Sekunde), obwohl natürlich alle weiteren Vorschläge noch willkommen wäre ...

Answer 3

Sie können Ihre „is_prime“ Funktion durch die Verwendung eines probabilistischen Algorithmus beschleunigen. Eine der einfachsten schnellen Algorithmen hierfür ist die Miller-Rabin Algorithmus.

Answer 4

die Hälfte Ihrer Berechnungen loszuwerden Sie auch die Reihe der möglichen a's machen konnten nur ungeradee Zahlen enthalten

Answer 5

meine super Python Lösung: 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()