SAlut,
OK ! Voilà :
Résultat :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 # usr/bin/env python # -*- coding: utf-8 -*- def eratosthene(n,premiers): nombres = [] for i in xrange(2,n+1): nombres.append(True) # affecte True à tous les nombres de 2 à n for i in xrange(2,n+1): if nombres[i-2]: # décalage de 2, entre l'indice et le nombre, donc son état # Si le nombre i, d'indice i-2, est à TRUE premiers.append(i) # C'est un premier for j in xrange(2*i,n+1,i): # On boucle donc sur tous ses multiples jusqu'à la imite n fixée nombres[j-2] = False # Et on les passe à False return premiers,nombres n,premiers=100,[] premiers,z=eratosthene(n,[]) # Pour te faire une idée du fonctionnement print premiers print print z
C'et beau, surprenant... et très rapide ! Hélas, ça n'est pas de moi...[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]
[True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, False, False, True, False, False, False]
En fait, l'algo commence par affecter TRUE à 2,3,4,5,6... n etc (dans l'exemple n = 100), ce qui est vrai déjà pour 2 et 3 : la pompe est amorcée.
On interroge 2 sur son état en cherchant nombres(2-2) on trouve TRUE, on le stocke dans premiers, et on parcourt la liste des nombres à partir de 2 et pas par de 2, et on les passe à FALSE : 4,6,8,10,12.... sont donc devenus FALSE.
Idem pour 3, sauf que 6 est déjà FALSE pas besoin de le retraiter...
On arrive à 4 : il a été passé à FALSE, on continue...
Quand on arrive à 17 (par ex.), puisqu'il resté à TRUE, c'est qu'il n'est pas multiple des nombres premiers qui le précèdent, il est donc bien premier.
En utilisation "normale", tu te contentes :
1. d'écrire : return premiers
2. de récupérer premiers et laisser z : premiers = eratosthene(n, [])
C'est clair ?
Bon j'espère que cette "publication" ne gêne personne...
@+
Partager