Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

Différences

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

Lien vers cette vue comparative

--- liste_des_nombres_premiers [2009/11/17 09:00]
tyrtamos
+++ liste_des_nombres_premiers [2012/04/04 06:53]
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érieurs 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 tous 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 =====
@@ Ligne 37: / Ligne 219: @@
 - A part "2" qui est premier, on ne teste pas les nombres pairs qui ne sont forcément pas premiers.
-- Pour chaque nombre k à tester, On arrête les divisions à racine de k parce que si on n'a pas encore trouvé de diviseur, on n'en trouvera plus après, et le nombre est donc premier. C'est ce point qui justifie l'importation du module math.
+- Pour chaque nombre k à tester, On arrête les divisions à racine de k parce que si on n'a pas encore trouvé de diviseur, on n'en trouvera plus après, et le nombre est donc premier.
 - Comme on doit conserver tous les nombres premiers trouvés, on n'utilise qu'eux comme diviseur dans les tests de division!
@@ Ligne 46: / Ligne 228: @@
 <code python>
-def lrac2(x):
-    """Racine carrée entiere d'un nombre entier x (méth. de Héron d'Alexandrie)"""
-    r1 = 1
-    while True:
-        r2 = (r1+x//r1)//2
-        if abs(r1-r2) < 2:
-            if r1*r1 <= x and (r1+1)*(r1+1) > x:
-                return r1
-        r1 = r2
 def premiers(n, p=[2,3,5]):
-    """Retourne la liste des nombres premiers <= n"""
+    """Retourne la liste des nombres premiers <= n (méthode=division)"""
     k = p[-1]+2
     if n < k:
         return [x for x in p if x<=n]
     while k <= n:
-        rk = lrac2(k)+1
         i = 0
         while i < len(p):
-            if p[i] > rk:
+            if p[i]*p[i] > k:
                 p.append(k)
                 break
@@ Ligne 78: / Ligne 249: @@
 </code>
-On a besoin d'une fonction qui donne la racine carrée entière de k. J'ai mis ici la fonction qui vient d'Héron d'Alexandrie, mais on peut utiliser aussi une fonction qui utilise la dichotomie (voir ailleurs sur ce site).
+Performance: Cette fonction est très rapide. Par exemple, toujours avec l'accélérateur psyco, la fonction trouve les 5.761.455 nombres premiers inférieurs à 100 millions en une centaine de secondes. A noter que l'affichage de cette très longue liste sera plus longue que son calcul...
-Performance: Cette fonction est très rapide. Par exemple, toujours avec l'accélérateur psyco, la fonction trouve les 664.579 nombres premiers inférieurs à 10 millions en une dizaine de seconde. A noter que l'affichage de cette très longue liste sera plus longue que son calcul...
-Avec cette fonction, on peut avoir n=1 milliard, et on trouve alors les 50.847.534 nombres premiers en à peu près 1 heure. Mais il ne faut pas rêver: le temps de calcul grimpe très très vite, et ce n'est pas avec ça que vous allez casser le cryptage RSA: le dernier cryptage factorisé, le RSA-640, a demandé plus de 5 mois de calcul avec 30 CPU ... Et on en est maintenant au RSA-2048!
-Possibilité d'amélioration de la performance: si on pouvait utiliser une liste de nombres premiers déjà calculée auparavant et sauvegardée sur disque, on gagnerait du temps! A voir pour une prochaine version (elle est déjà bien avancée!).
+Avec cette fonction, on peut avoir n=1 milliard, et on trouve alors les 50.847.534 nombres premiers en à peu près 40 minutes. Mais il ne faut pas rêver: le temps de calcul grimpe très très vite, et ce n'est pas avec ça que vous allez casser le cryptage RSA: le dernier cryptage factorisé, le RSA-640, a demandé plus de 5 mois de calcul avec 30 CPU ... Et on en est maintenant au RSA-2048 qui correspond à un nombre d'environ 600 chiffres!
 Cas particulier: si n=1, la fonction renvoie une liste vide, parce que "1" n'est pas un nombre premier.
@@ Ligne 91: / Ligne 258: @@
 \\
-Vous pouvez tester cette fonction avec la Calculext ici: [[http://calculext.jpvweb.com]], mais soyez raisonnable: au delà de premiers(100000), vous allez dépasser le temps maxi de calcul autorisé sur le serveur (qui, de plus, n'a pas psyco).
+Vous pouvez tester cette fonction avec la Calculext ici: [[http://calculext.jpvweb.com]], mais soyez raisonnable: au delà de premiers(100000), vous allez dépasser le temps maxi (8s) de calcul autorisé sur le serveur (qui, de plus, n'a pas psyco).

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page