Projet Euler Problème 27 F #

Question

J'ai essayé de me frayer un chemin à travers Problème 27 de Euler projet, mais celui-ci semble me dessouchage. Tout d'abord, le code prend beaucoup trop de temps à courir (quelques minutes peut-être, sur ma machine, mais plus important encore, il est de retour la mauvaise réponse que je ne peux vraiment pas repérer quelque chose de mal avec l'algorithme après avoir regardé à travers elle pendant un certain temps .

Voici mon code actuel pour la solution.

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

Les conseils sur la façon a) obtenir cet algorithme fait revenir la bonne réponse (je pense que je suis au moins une approche viable) et b) améliorer les performances, car il dépasse clairement la « une minutes de punition dans » prévue dans la FAQ du projet Euler. Je suis un peu d'un débutant à la programmation fonctionnelle, donc des conseils sur la façon dont je pourrais considérer le problème avec une solution plus fonctionnelle à l'esprit serait également appréciée.

Answer 1

Deux remarques:

1. Vous pouvez profiter du fait que b doit être premier . Cela découle du fait que le problème demande la plus longue séquence de nombres premiers pour n = 0, 1, 2, ... Ainsi, formula(0) doit être premier pour commencer, mais formula(0) = b donc b doit être premier.

2. Je ne suis pas un programmeur F #, mais il me semble que le code ne cherche pas n = 0 du tout . Ceci, bien sûr, ne répond pas à l'exigence du problème n doit partir 0, donc il y a des chances pourrait être produit négligeable une réponse correcte.

Answer 2

Droit, après beaucoup de vérifier que toutes les fonctions d'aide faisaient ce qu'ils devraient, je l'ai finalement atteint une solution de travail (et raisonnablement efficace).

Tout d'abord, le is_prime fonction était complètement faux (grâce à Dimitre Novatchev pour me faire regarde ça). Je ne sais pas vraiment comment je suis arrivé à la fonction que j'ai posté dans la question initiale, mais je l'avais supposé qu'il travaillait depuis que je l'avais utilisé dans les problèmes précédents. (Très probablement, je venais peaufiné et brisé depuis.) Quoi qu'il en soit, la version de travail de cette fonction (qui renvoie fondamentalement faux pour tous les entiers inférieurs à 2) est la suivante:

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

La fonction principale a été changé à ce qui suit:

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

La clé ici pour augmenter la vitesse était de générer que l'ensemble des nombres premiers entre 1 et 1000 pour les valeurs de b (en utilisant les nombres premiers fonction, ma mise en œuvre du Crible d'Ératosthène procédé). J'ai aussi réussi à rendre ce code un peu plus concis en éliminant la Seq.map inutile.

Alors, je suis assez satisfait de la solution que j'ai maintenant (il faut juste moins d'une seconde), mais bien sûr d'autres suggestions seraient toujours les bienvenus ...

Answer 3

Vous pouvez accélérer votre fonction « is_prime » en utilisant un algorithme probabiliste. L'un des plus simples algorithmes rapides pour c'est l'algorithme de Miller-Rabin.

Answer 4

pour se débarrasser de la moitié de vos calculs, vous pouvez aussi faire le choix de a's possibles ne contiennent que des nombres impairs

Answer 5

ma solution python ultra-rapide: 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()