Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
liste_des_nombres_premiers [2009/11/17 15:35] 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:// | Pour la définition de ce qu'est un nombre premier, voir ici: [[http:// | ||
- | 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 |
- | | + | premiers(100) => [2, |
+ | |||
+ | Combien y a-t-il de nombres premiers? Une infinité. Voilà quelques exemples: | ||
+ | |||
+ | < | ||
+ | nombres de nombres premiers inférieurs 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 | ||
+ | 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 | ||
+ | </ | ||
+ | |||
+ | 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 " | ===== Méthode du " | ||
Ligne 11: | Ligne 41: | ||
Le principe du calcul est indiqué ici: [[http:// | Le principe du calcul est indiqué ici: [[http:// | ||
- | A part la version récursive, que je n' | + | Commençons par un code simple |
<code python> | <code python> | ||
- | def premiers(n): | + | def eratosthene(n): |
- | """""" | + | """ |
- | | + | n += 1 |
- | | + | |
- | k = 2 | + | |
- | | + | |
- | | + | # 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] | + | |
+ | return [p for p in tableau | ||
</ | </ | ||
- | Cette version est de plus très rapide. Par exemple, avec l' | + | Le code se lit bien: |
+ | |||
+ | * on crée une liste de nombres comme [0, | ||
+ | * le nombre d' | ||
+ | * 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' | ||
+ | |||
+ | * 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/ | ||
+ | |||
+ | Voilà un tel code amélioré: | ||
+ | |||
+ | <code python> | ||
+ | def eratosthene(n): | ||
+ | """ | ||
+ | if n<2: | ||
+ | return [] | ||
+ | n += 1 | ||
+ | tableau = [False, | ||
+ | tableau[2:: | ||
+ | premiers = [2] # initialisation de la tableau des nb 1ers (2 est 1er) | ||
+ | racine = int(n**0.5) | ||
+ | racine = racine + [1, | ||
+ | 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:: | ||
+ | for i in xrange(racine, | ||
+ | if tableau[i]: | ||
+ | # on enregistre le nouveau nb 1er (pas de multiples à supprimer) | ||
+ | premiers.append(i) | ||
+ | return premiers | ||
+ | </ | ||
+ | |||
+ | 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, | ||
+ | |||
+ | Pour contourner ce problème de mémoire, commençons par créer un itérateur pour éviter d' | ||
+ | |||
+ | <code python> | ||
+ | def eratosthene_iter(n): | ||
+ | """ | ||
+ | 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:: | ||
+ | yield 2 # 2 est un nombre premier | ||
+ | racine = int(n**0.5) | ||
+ | racine = racine + [1, | ||
+ | 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 += pas | ||
+ | i, fin, pas = racine, n, 2 | ||
+ | while i< | ||
+ | if tableau[i]: | ||
+ | yield i # i est un nombre premier | ||
+ | i += pas | ||
+ | </ | ||
+ | |||
+ | Comme c'est un itérateur, le plus naturel est de l' | ||
+ | |||
+ | <code python> | ||
+ | for p in eratosthene_iter(100): | ||
+ | print p | ||
+ | </ | ||
+ | |||
+ | Mais on peut, à la rigueur, l' | ||
+ | |||
+ | <code python> | ||
+ | gen = eratosthene_iter(100) | ||
+ | while True: | ||
+ | try: | ||
+ | print gen.next() | ||
+ | except StopIteration: | ||
+ | break | ||
+ | </ | ||
+ | |||
+ | 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)] | ||
+ | </ | ||
+ | |||
+ | On peut même créer une fonction lambda: | ||
+ | |||
+ | <code python> | ||
+ | premiers = lambda n: [p for p in eratosthene_iter(n)] | ||
+ | </ | ||
+ | |||
+ | Ce code est très rapide, mais le tableau consomme encore beaucoup de mémoire. | ||
+ | |||
+ | Alors, on peut utiliser le module " | ||
+ | |||
+ | On trouve ce module ici: [[http:// | ||
+ | |||
+ | Voilà le nouveau et dernier code, toujours sous forme d' | ||
+ | |||
+ | <code python> | ||
+ | def eratosthene_ba_iter(n): | ||
+ | """ | ||
+ | on utilise ici le module ' | ||
+ | """ | ||
+ | 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:: | ||
+ | racine = int(n**0.5) | ||
+ | racine = racine + [1, | ||
+ | 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 += pas | ||
+ | i, fin, pas = racine, n, 2 | ||
+ | while i< | ||
+ | if tableau[i]: | ||
+ | yield i # on a trouvé un nouveau nb 1er: on le renvoie | ||
+ | i += pas | ||
+ | </ | ||
+ | |||
+ | 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)] | ||
+ | </ | ||
+ | |||
+ | On peut même créer une fonction lambda: | ||
+ | |||
+ | <code python> | ||
+ | premiers = lambda n: [p for p in eratosthene_ba_iter(n)] | ||
+ | </ | ||
+ | |||
+ | Cette dernière fonction est vraiment rapide et permet d' | ||
+ | |||
+ | 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, | ||
===== Méthode par divisions systématiques ===== | ===== Méthode par divisions systématiques ===== |