Euler 007

Publié le 22/12/16

Soit {n} dans {\mathbb{N}^{*}}.
Écrire une fonction renvoyant le {n}-ième nombre premier.
Remarque: l’énoncé original du Project Euler se limite à {n=10001}.
Le résultat est alors {104743}.
  1. Première solution

    Voici un exemple d’utilisation:

    >>> euler007a(10001)
    Le 10001-ième nombre premier est 104743
    Résultat obtenu en 0.492 secondes

    >>> euler007a(50000)
    Le 50000-ième nombre premier est 611953
    Résultat obtenu en 4.917 secondes

    >>> euler007a(100000)
    Le 100000-ième nombre premier est 1299709
    Résultat obtenu en 12.679 secondes

    >>> euler007a(200000)
    Le 200000-ième nombre premier est 2750159
    Résultat obtenu en 41.981 secondes

  2. Deuxième solution

    La solution suivante est plus compacte que la précédente, mais elle est bien sûr moins lisible (elle se comprend quand même assez bien si on la compare à la solution précédente, avec qui elle partage quelques notations).

    Entre les deux premières solutions, les temps de calcul sont très proches.

    À titre de comparaison, on a repris ici les mêmes exemples d’utilisation :

    >>> euler007b(10001)
    Le 10001-ième nombre premier est 104743
    Résultat obtenu en 0.431 secondes

    >>> euler007b(50000)
    Le 50000-ième nombre premier est 611953
    Résultat obtenu en 4.703 secondes

    >>> euler007b(100000)
    Le 100000-ième nombre premier est 1299709
    Résultat obtenu en 13.666 secondes

    >>> euler007b(200000)
    Le 200000-ième nombre premier est 2750159
    Résultat obtenu en 39.876 secondes

  3. Troisième solution

    Cette troisième solution est la plus rapide.

    L’amélioration consiste à former progressivement une liste d’entiers premiers: chaque nouvel entier {k} est déclaré premier (et donc ajouté à la liste) quand on constate qu’il n’est divisible par aucun des entiers premiers {j} connus à ce stade (en se limitant bien sûr à ceux qui sont inférieurs ou égaux à {\sqrt{k}}).

    Cette méthode impose bien sûr de gérer une liste primes qui s’enrichit progressivement de nouveaux entiers premiers, mais le coût induit est largement compensé par le fait qu’il n’est plus nécessaire de tester la divisibilité de {k} par tous les entiers impairs {j} de l’intervalle {[3,\sqrt{k}]}.

    La fonction premier de la solution n\degre1 est ici remplacée par une fonction primable qui teste si un entier {k} n’est divisible par aucun des entiers {j} de la liste primes (en se limitant, on l’a dit à {j\le\sqrt{n}}). Dans le déroulement des calculs, un entier {k} est déclaré primable, donc ajouté à la liste primes, si et seulement si il est premier.

    On reprend les mêmes exemples d’utilisation:

    euler007c(10001)
    Le 10001-ième nombre premier est 104743
    Résultat obtenu en 0.249 secondes

    >>> euler007c(50000)
    Le 50000-ième nombre premier est 611953
    Résultat obtenu en 1.931 secondes

    >>> euler007c(100000)
    Le 100000-ième nombre premier est 1299709
    Résultat obtenu en 5.008 secondes

    >>> euler007c(200000)
    Le 200000-ième nombre premier est 2750159
    Résultat obtenu en 13.388 secondes