Différences

Ci-dessous, les différences entre deux révisions de la page.

--- liste_des_nombres_premiers [2009/11/17 15:35]
tyrtamos
+++ liste_des_nombres_premiers [2012/04/03 06:51]
tyrtamos
@@ Ligne 3: / Ligne 3: @@
 Pour la définition de ce qu'est un nombre premier, voir ici: [[http://fr.wikipedia.org/wiki/Nombre_premier]]
-Les fonctions présentées ici renverront la liste des nombres premiers. Par exemple:
+Les fonctions présentées ici renverront la liste des nombres premiers inférieurs à un nombre donné. Par exemple, pour ceux inférieurs à 100:
-  premiers(100) => [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
+premiers(100) => [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
+Combien y a-t-il de nombres premiers? Une infinité. Voilà quelques exemples:
+<code>
+nombres de nombres premiers inférieur ou égaux à 10**n:
+**1  4
+**2  25
+**3  168
+**4  1229
+**5  9592
+**6  78498
+**7  664579
+**8  5761455
+**9  50847534
+**10 455052511  <= ok
+**11 4118054813
+**12 37607912018
+**13 346065536839
+**14 3204941750802
+**15 29844570422669
+**16 279238341033925
+**17 2623557157654233
+**18 24739954287740860
+**19 234057667276344607
+**20 2220819602560918840
+</code>
+Avec le code le plus rapide parmi ceux de cette page, on peut trouver les 455052511 nombres premiers inférieurs ou égaux à 10 milliards en une heure environ.
+Au delà, il faudra une grosse mémoire et beaucoup de patience...
 ===== Méthode du "crible d'Eratosthène" =====
@@ Ligne 11: / Ligne 41: @@
 Le principe du calcul est indiqué ici: [[http://fr.wikipedia.org/wiki/Crible_d'%C3%89ratosth%C3%A8ne]]
-A part la version récursive, que je n'utilise pas à cause des limites de Python (pile<1000), la version la plus efficace et la plus élégante que j'ai trouvée sur le web est la suivante:
+Commençons par un code simple et très proche du principe de base:
 <code python>
-def premiers(n):
+def eratosthene(n):
-    """"""
+    """retourne la tableau des nombres premiers <= n (crible d'eratosthene)"""
-    L = range(0,n+1)
+    n += 1
-    L[1] = 0
+    tableau = [0,0] + [i for i in xrange(2, n)]
-    k = 2
+    for i in xrange(2, n):
-    while k*k <= n:
+        if tableau[i] != 0:
-        L[k*2::k] = [0]*len(L[k*2::k])
+            # c'est un nombre 1er: on garde, mais on neutralise ses multiples
-        k += 1
+            for j in xrange(i*2, n, i):
-    return [x for x in L if x]
+                tableau[j] = 0
+    return [p for p in tableau if p!=0]
 </code>
-Cette version est de plus très rapide. Par exemple, avec l'accélérateur psyco, on trouve les 664579 nombres premiers inférieurs à 10 millions en une dizaine de secondes!!!
+Le code se lit bien:
+  * on crée une liste de nombres comme [0,0,2,3,4,5,6,7,8,9,10,...]
+  * le nombre d'indice 1 est 0, parce que 1 n'est pas un nombre premier
+  * on progresse dans la liste, et à chaque fois qu'on trouve un nombre différent de 0: c'est un nombre premier, et on met à 0 ses multiples
+  * à la fin, on retourne le liste de tous les nombres qui ne sont pas à 0
+C'est déjà un code rapide, mais on peut l'améliorer:
+  * une fois le nombre 2 identifié comme premier, on ne testera plus que les nombres impairs
+  * dans la boucle de test, une fois qu'on a atteint un nombre premier supérieur à racine de n, il n'y a plus de multiple à supprimer
+  * dans le tableau, on va plutôt contenir des booléens (True/False) que des nombres
+Voilà un tel code amélioré:
+<code python>
+def eratosthene(n):
+    """retourne la liste des nombres premiers <= n (crible d'eratosthene)"""
+    if n<2:
+        return []
+    n += 1
+    tableau = [False,False] + [True]*(n-2)
+    tableau[2::2] = [False]*((n-2)//2 + n%2) # sup. des nb pairs
+    premiers = [2] # initialisation de la tableau des nb 1ers (2 est 1er)
+    racine = int(n**0.5)
+    racine = racine + [1,0][racine%2] # pour que racine soit impair
+    for i in xrange(3, racine+1, 2):
+        if tableau[i]:
+            # on enregistre le nouveau nb 1er
+            premiers.append(i)
+            # on élimine i et ses multiples
+            tableau[i::i] = [False]*((n-i)//i + int((n-i)%i>0))
+    for i in xrange(racine, n, 2):
+        if tableau[i]:
+            # on enregistre le nouveau nb 1er (pas de multiples à supprimer)
+            premiers.append(i)
+    return premiers
+</code>
+Cette version est de plus très rapide. Par exemple, on trouve les 664579 nombres premiers inférieurs à 10 millions en une seule seconde!!! Et les 5761455 nombres premiers inférieurs à 100 millions en une dizaine de secondes.
+Mais au delà, malheureusement, cette méthode consomme beaucoup de mémoire et génère une exception "MemoryError".
+Pour contourner ce problème de mémoire, commençons par créer un itérateur pour éviter d'avoir à contenir en mémoire toute la liste des nombres premiers:
+<code python>
+def eratosthene_iter(n):
+    """Itérateur retourne tous les nb premiers <= n (crible d'Eratosthene)"""
+    if n<2:
+        pass # il n'y a aucun nb 1er en dessous de 2!
+    else:
+        n += 1 # pour avoir les nb 1ers <=n et pas seulement <n
+        tableau = [False, False] + [True]*(n-2)
+        tableau[2::2] = [False]*((n-2)//2 + n%2) # supr. des nb pairs
+        yield 2 # 2 est un nombre premier
+        racine = int(n**0.5)
+        racine = racine + [1,0][racine%2] # pour que racine soit impair
+        i, fin, pas = 3, racine+1, 2
+        while i<fin: # on ne traite que les nb impairs
+            if tableau[i]:
+                yield i # i est un nombre premier
+                # on élimine i et ses multiples
+                tableau[i::i] = [False]*((n-i)//i + int((n-i)%i>0))
+            i += pas
+        i, fin, pas = racine, n, 2
+        while i<fin:  # on ne traite que les nb impairs
+            if tableau[i]:
+                yield i # i est un nombre premier
+            i += pas
+</code>
+Comme c'est un itérateur, le plus naturel est de l'utiliser dans une boucle for:
+<code python>
+for p in eratosthene_iter(100):
+    print p
+</code>
+Mais on peut, à la rigueur, l'utiliser comme suit:
+<code python>
+gen = eratosthene_iter(100)
+while True:
+    try:
+        print gen.next()
+    except StopIteration:
+        break
+</code>
+Comme c'est un itérateur, on peut toujours retrouver la liste complète des nombres renvoyés:
+<code python>
+premiers = [p for p in eratosthene_iter(1000)]
+</code>
+On peut même créer une fonction lambda:
+<code python>
+premiers = lambda n: [p for p in eratosthene_iter(n)]
+</code>
+Ce code est très rapide, mais le tableau consomme encore beaucoup de mémoire.
+Alors, on peut utiliser le module "bitarray' qui ne prend qu'un seul bit pour stocker chaque valeur booléenne.
+On trouve ce module ici: [[http://pypi.python.org/pypi/bitarray]]. Sous Windows, il faut l'installer avec setuptools.
+Voilà le nouveau et dernier code, toujours sous forme d'itérateur:
+<code python>
+def eratosthene_ba_iter(n):
+    """Itérateur retourne tous les nb premiers <= n (crible d'Eratosthene)
+       on utilise ici le module 'bitarray' pour stocker les booléens
+    """
+    if n<2:
+        pass # il n'y a aucun nb 1er en dessous de 2!
+    else:
+        n += 1 # pour avoir les nb 1ers <=n et pas seulement <n
+        tableau = bitarray(n)
+        tableau.setall(True)
+        tableau[0], tableau[1] = False, False # 1 n'est pas un nb 1er
+        yield 2  # 2 est un nombre premier
+        tableau[2::2] = False # on élimine tous les nombres pairs
+        racine = int(n**0.5)
+        racine = racine + [1,0][racine%2] # pour que racine de n soit impair
+        i, fin, pas = 3, racine+1, 2
+        while i<fin: # on ne traite que les nb impairs
+            if tableau[i]:
+                yield i # on a trouvé un nouveau nb 1er: on le renvoie
+                tableau[i::i] = False # on élimine i et ses multiples
+            i += pas
+        i, fin, pas = racine, n, 2
+        while i<fin:  # on ne traite que les nb impairs
+            if tableau[i]:
+                yield i # on a trouvé un nouveau nb 1er: on le renvoie
+            i += pas
+</code>
+Comme c'est un itérateur, on peut toujours retrouver la liste complète des nombres renvoyés:
+<code python>
+premiers = [p for p in eratosthene_ba_iter(1000)]
+</code>
+On peut même créer une fonction lambda:
+<code python>
+premiers = lambda n: [p for p in eratosthene_ba_iter(n)]
+</code>
+Cette dernière fonction est vraiment rapide et permet d'obtenir, par exemple, //**les 455052511 nombres premiers inférieurs à 10 milliard en une heure environ**//.
+Il faut bien se rendre compte de ce que représentent une telle quantité de nombres: //un fichier de 5,03 Go// (5 403 267 048 octets)!
-Malheureusement, cette méthode a une limite: malgré une mémoire "confortable" (2Go), mon Python refuse d'exécuter avec n > 10 millions environ.
 ===== Méthode par divisions systématiques =====

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page