Warning: Undefined array key "DOKU_PREFS" in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/common.php on line 2082
liste_des_nombres_premiers [Les recettes Python de Tyrtamos]

Outils pour utilisateurs

Outils du site


liste_des_nombres_premiers

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision
Révision précédente
Dernière révision Les deux révisions suivantes
liste_des_nombres_premiers [2008/07/02 17:17]
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]] 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: 
 +10**1  4 
 +10**2  25 
 +10**3  168 
 +10**4  1229 
 +10**5  9592 
 +10**6  78498 
 +10**7  664579 
 +10**8  5761455 
 +10**9  50847534 
 +10**10 455052511  <= ok 
 +10**11 4118054813 
 +10**12 37607912018 
 +10**13 346065536839 
 +10**14 3204941750802 
 +10**15 29844570422669 
 +10**16 279238341033925 
 +10**17 2623557157654233 
 +10**18 24739954287740860 
 +10**19 234057667276344607 
 +10**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" ===== ===== 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]] 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> <code python>
-def premiers(n): +def eratosthene(n): 
-    """"""       +    """retourne la tableau des nombres premiers <= n (crible d'eratosthene)""" 
-    L = range(0,n+1) +    n +
-    L[1] = 0 +    tableau [0,0] + [i for i in xrange(2, n)] 
-    k = +    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 [for in if x]+                tableau[j] 0 
 +    return [for in tableau if p!=0       
 </code> </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 9.30 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 ===== ===== 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. - 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! - 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> <code python>
-#!/usr/bin/python +def premiers(n, p=[2,3,5]): 
-# -*- coding: utf-8 -*- +    """Retourne la liste des nombres premiers <= n (méthode=division)""" 
- +    p[-1]+
-from math import * +    if n < k
- +        return [x for x in p if x<=n
-def premiers(n): +    while k <= n: 
-    """premiers(n): trouve tous les nombres premiers <= n et les affiche sous forme d'une liste""" +        i = 0 
-    if n==1+        while i < len(p): 
-        return [] +            if p[i]*p[i] > k:
-    if n==2+
-        return [2] +
-    if n in (3,4)+
-        return [2,3] +
-    if n in (5,6): +
-        return [2,3,5] +
-    p=[2,3,5] +
-    k=7 +
-    while k<=n: +
-        rk=int(sqrt(k))+1 +
-        i=0 +
-        while i<len(p): +
-            if p[i]>rk:+
                 p.append(k)                 p.append(k)
                 break                 break
-            if (k % p[i])==0:+            if (k % p[i]) == 0:
                 break                 break
-            i+=1 +            i += 1 
-        k+=2+        k += 2
     return p     return p
  
Ligne 80: Ligne 249:
 </code> </code>
  
-Performance: Cette fonction est plus rapide que le crible d'Eratosthène pour des valeurs fortes. Par exemple, toujours avec l'accélérateur psyco, la fonction trouve les 664.579 nombres premiers inférieurs à 10 millions en 6.85 secondes soit 26% plus rapide. 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 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...
- +
-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. 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).
  
  
liste_des_nombres_premiers.txt · Dernière modification: 2012/04/04 06:53 de tyrtamos