Euler 010

Publié le 22/12/16

Soit {N\ge3} un entier.
Trouver la somme des entiers premiers strictement inférieurs à {N}.
L’énoncé original du « Project Euler » se limite à {N=2000000}.
La réponse est alors {142913828922}.
  1. Première solution

    On reprend un programme très proche de la troisième solution du problème Euler007.

    Voici un exemple d’utilisation, avec N=2000000:
    >>> euler010a(2000000)
    La somme des entiers p premiers, avec p < 2000000, est 142913828922 Résultat obtenu en 8.576 secondes

  2. Deuxième solution

    On utilise ici le crible d'Erathostène. On forme une liste de valeurs booléennes (au départ toutes égales à False) pour indiquer si un entier {n} a été marqué comme premier (avec {0\le n \lt N}).

    Voici un exemple, toujours avec {N=2000000}. Malgré le coût induit par la construction de la liste de {N} booléens, le résultat est plus rapide qu'avec la première méthode (qui était pénalisée par les modifications de la liste primes).
    >>> euler010b(2000000)
    La somme des entiers p premiers, avec p < 2000000, est 142913828922 Résultat obtenu en 0.893 secondes