Discussion :

[yoshik]

SAlut,

OK ! Voilà :

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

Résultat :

[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]

C'et beau, surprenant... et très rapide ! Hélas, ça n'est pas de moi...
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...

@+

[nardo47]

Bon j'espère que cette "publication" ne gêne personne...

Pas moi, d'autant + que je l'avais déjà

Par contre, je n'ai jamais sorti la liste des nombres premiers, j'ai toujours gardé le tableau sieve = [False, False, True, True, False, True, ...] tel que, et je regardais la primalité d'un nombre n en faisant simplement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
if sieve[n]:
    print n, 'est premier!'
 
# ce qui me fait penser qu'on peut avoir la liste des n nombres premiers en faisant :
[i for i, p in enumerate(sieve) if p]

Ah si, je commence l'initialisation du tableau différemment :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
# n est la limite du crible
sieve = [False] * (n + 1) # N'oublions pas qu'un tableau commence par l'indice 0.
sieve[0] = sieve[1] = False # 0 et 1 ne sont pas premiers.
for x in xrange(4, n + 1, 2):
    sieve[x] = False # Les nombres pairs ne sont pas premiers, 2 excepté.
# le reste étant peu ou prou ce qu'a écrit Yoshik.
 
# Et, maintenant  que j'y pense, j'aurais pu initialiser mon tableau comme ceci :
sieve = [False, True] * (n / 2 + 1) # (n // 2 + 1) en Python 3
sieve[1] = False
sieve[2] = True
# ce qui évite de faire une boucle pour indiquer que tous les nombres pairs ne sont pas premiers.

Je sais, ma deuxième version fait vraiment chipotage, mais il me semble que l'on parle d'optimisation, par ici.

N.B. j'appelle mon tableau sieve, qui est la traduction anglaise de crible (hop, une recherche "crible eratosthene" vous donnera toutes les infos !

[nardo47]

En utilisation "normale", tu te contentes :
1. d'écrire : return premiers
2. de récupérer premiers et laisser z : premiers = eratosthene(n, [])

Même pas !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
premiers = []
eratosthene(n, premiers)

Ceci devrait suffire : premiers est une liste, donc mutable. Comme append ne renvoie pas de valeur (elle modifie la liste sur place) et que Python ne fait que des passages par référence, tu ne devrais pas avoir besoin de retourner quoi que ce soit !
Ceci est purement théorique, je n'ai pas testé ton code.

[yoshik]

SAlut,

Merci ! Intéressant ! Ton histoire de mutable, va falloir que je regarde ça de plus près : c'est la deuxième référence qu'on m'y fait en une semaine...Pour l'instant, c'est flou !
Bon, effectivement tu as raison, à condition comme tu l'indiques eratosthene(n,premiers) et non pas comme je je l'ai fait :
eratosthene(n,[]) qui me renvoie une liste vide, ce qui me fait penser que ce dernier procédé est plus gourmand en mémoire, parce que si j'ai bien compris, il n'y a pas une liste nommée premiers quand j'appelle
premiers=eratosthene(n,[]) mais 2 :
une dans le corps du programme et une autre locale dans le def...
Si c'est bien exact, j'ai utilisé jusqu'à maintenant une procédure "impropre" dans sa conception.

Mes soupçons sont-ils fondés ou pas ? Ô amateurs éclairés et chevronnés que je vois passer régulièrement, voulez-vous infirmer ou confirmer.

D'autre part, si ma liste de nombres premiers a besoin dêtre abondée au coup par coup (sans avoir besoin de la reconstruire à chaque fois du début) puis-je remplacer return par yield ?
Il faudrait que j'essaie...

@+

PS
Nan ! Marche pas !
Soit il ne renvoie rien : affichage vide, soit j'ai droit à :
<generator object eratosthene at 0x011B8C38>

Ah m.... alors !!

[yoshik]

A supprimer : erreur ! Merci !
Pas de bouton "Supprimer" sur ce forum ?

[rambc]

Voici une petite amélioration en termes de rapidité :

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#!/usr/bin/env python
#coding=utf-8
 
from time import clock
 
def eratosthene_1(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
 
def eratosthene_2(n):
    """
    Here we just work woth odd natural numbers.
    
    numbers[i]   0  1  2
    N            3  5  7...
    
    We have i = N//2 - 1
    """
    premiers = [2]
 
    if str(n)[-1] in ['0', '2', '4', '6', '8']:
        i_max = n/2 - 1
    else:
        i_max = n/2
 
    nombres = ['True']*i_max
 
    for i in xrange(i_max):
        if nombres[i]:
# Cf. doc string ci-dessus.
            premiers.append(2*i + 3)
# Si n = 3, on élimine n + 2n = 9 , n + 4n = 15 ,... etc
# On va donc de 2n en 2n.
#
# En terme d'indice, cela devient :
#    n = 2*i+3  <==>  i = (n-3)//2
#    3n = 2*j+3 , 3n = 6*i+9 <==>  2*j+3 = 6*i+9
#                            <==>  2*j = 6*i+6
#                            <==>  j = 3*i+3  -->  PAS = 2*i+3
#    5n = 2*k+3 , 5n = 10*i+15 <==>  2*k+3 = 10*i+15
#                              <==>  2*k = 10*i+12
#                              <==>  k = 5*i+6  -->  PAS = 2*i+3
            pas = 2*i+3
# L'intérêt est que le pas devient de plus en plus en grand
# en même temps que les nouveaux nombres premiers découverts.
# Du coup, on fait moins de testes inutiles.
            for j in xrange(i,i_max,pas):
                nombres[j] = False
    return premiers
 
 
 
n = 1000000
 
timeStart = clock()
premiers_1 = eratosthene_1(n)
timeEnd = clock()
 
print '=== METHODE 1'
print '\t'*5 + ' Temps : ' + str(timeEnd - timeStart)
print '\t'*5 + ' Dernier premier trouve : ' + str(premiers_1[-1])
 
timeStart = clock()
premiers_2 = eratosthene_2(n)
timeEnd = clock()
 
print '=== METHODE 2'
print '\t'*5 + ' Temps : ' + str(timeEnd - timeStart)
print '\t'*5 + ' Dernier premier trouve : ' + str(premiers_2[-1])
 
print '=== COMPARAISON DES METHODES'
print '\t'*5 + ' premiers_1 = premiers_2 : ' + str(premiers_1 == premiers_2)

J'ai obtenu :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
=== METHODE 1
					 Temps : 1.06
					 Dernier premier trouve : 999983
=== METHODE 2
					 Temps : 0.38
					 Dernier premier trouve : 999983
=== COMPARAISON DES METHODES
					 premiers_1 = premiers_2 : True

[rambc]

Hello a tous
Alors voila. Aprés avoir eu besoins de 11h30 de temps d'execution pour résoudre la question 12, j'ai (enfin) décidé de m'attaquer a un algo propre et efficace de décomposition en nombre premier.
Il semblerai que l'algo de rho-pollard soit pas mal...

Regardez cette page. Il faudrait voir si cela est rapide à programmer.

[nardo47]

eratosthene(n,[])

Ben, moi, perso, je veux bien que tu tapes ça, mais comment tu récupères le résultat ?

si j'ai bien compris, il n'y a pas une liste nommée premiers quand j'appelle
premiers=eratosthene(n,[]) mais 2 :
une dans le corps du programme et une autre locale dans le def...

En fait, non. Tu avais 2 références à cette liste, ce qui du coup n'est pas gourmand en mémoire.
Il faut bien comprendre que les variables en Python sont juste des références à des objets.
Après, je ne sais pas si le return fait une copie de l'objet (ce qui ne m'étonnerait pas) mais, même s'il le fait, le garbage collector devrait s'activer lors de la sortie de la fonction et nettoyer la liste "interne" à la fonction (attention, je suppute).

Si c'est bien exact, j'ai utilisé jusqu'à maintenant une procédure "impropre" dans sa conception.

Boaf.
1. On est tous passés par là ;
2. si tu n'as pas de contrainte de mémoire, je ne vois pas où est le problème ;
3. si ton programme produit le bon résultat, le principal (et le moins fun, donc le + ardu) est fait.

L'optimisation reste du "superflu", quoique toujours la partie la + intéressante et la + stimulante.

Sinon, histoire de pinailler un peu, il n'y a pas de procédure en Python, juste des fonctions.

Pour ta génération au coup par coup, je crois deviner que tu as réussi... et que tu as compris que tu avais réussi !

@rambc:
Pour avoir une idée + précise du temps d'exécution de tes fonctions, utilise le package timeit au lieu de relever l'heure "à la pogne".
Il fait tourner les tests plusieurs fois, et donc obtient une moyenne de temps d'exécution, ce qui est + valide qu'un one-shot, qui peut toujours être perturbé par ce que fait ton OS (genre, "ah ben tiens, il serait pas temps de relever les mails ?")

[yoshik]

Bonsoir,

@rambc : tu divises le temps par 3 : belle perf, merci !

@nardo47
J'ai employé "procédure" dans son acceptation du français pas de Python...

Pour ta génération au coup par coup, je crois deviner que tu as réussi... et que tu as compris que tu avais réussi !

Bin, non justement, ça devrait marcher, et je n'arrive pas à récupérer ma liste..
J'ai essayé :
yield premiers
en lieu et place de : return premiers

puis eratosthène(n,premiers)
print premiers

S'affiche alors: [] et je suis bien avancé...

Et si j'essaie à la place :
premiers=eratosthene(n, premiers)
j'obtiens : <generator object eratosthene at 0x011B8C60>
là, par contre, j'entrevois pourquoi ça cloche...

@+

[nardo47]

J'ai employé "procédure" dans son acceptation du français pas de Python...

yield premiers

Ah ! Alors:
yield renvoie une valeur et "se souvient" de l'état dans laquelle est la fonction lors de ce renvoi.
Ce qui fait que l'appel suivant à la fonction reprend à partir de ce point.

Et donc, on n'utilise pas yield pour retourner le résultat final, mais une partie du résultat.
Dans le cas d'une liste, on "yielde" chaque élément de la liste final au fur et à mesure de leur calcul.
Il faut donc que tu places ton yield au niveau du premiers.append que tu fais.

Du coup, cet appel de fonction se fait dans une boucle for :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
for x in eratosthene_yield(n):
    print x

Et là, tu va devenir accroc !

[rambc]

Pour avoir une idée + précise du temps d'exécution de tes fonctions, utilise le package timeit au lieu de relever l'heure "à la pogne".
Il fait tourner les tests plusieurs fois, et donc obtient une moyenne de temps d'exécution, ce qui est + valide qu'un one-shot, qui peut toujours être perturbé par ce que fait ton OS (genre, "ah ben tiens, il serait pas temps de relever les mails ?")

Merci pour cette info. Par contre je ne pense qu'optimiser un code soit superflu, j'essaye toujours de faire en sorte de limiter les dégâts.

[ju_bicycle]

Salut a tous
Merci a Yoshi et rambc et aux autres pour le crible...Ca marche pas mal. Avec tout ca je suis tombé sous les 2 secondes, avec un machine médiocre et sans psyco...
A comprarer avec les 11h30 de ma premiere version
Next!

[dahtah]

Juste pour info : un algo détaillé basé sur le crible est proposé dans Linux Mag de Novembre.

[ju_bicycle]

Hello a tous: Quelqu'un c'est penché sur le prob 15? Celui ou il faut compter les chemins possible dans le carré? J'ai toujours était trop nul pour ce genre de probleme, je ne visualise pas du tout les trucs.
Attention je ne demande surtout pas du code, mais plutot la logique derriere...Si quelqu'un a une idée...

[rambc]

Il faut juste savoir que l'on peut se déplacer soit vers la gauche ou la droite (soit -1, +1 en x), soit vers le bas ou le haut (soit -1, +1 en y). Dans le cas où les déplacements se font sans retour, ie toujours vers la droite et/ou vers le bas, il y a une formule mathématique. J'imagine qu'ici il est interdit de repasser par un point déjà visité pour éviter les boucles infinies. Effectivement, je viens de lire le problème en entier. Dans ce cas, les mathématiques ont une réponse mais là je ne dirais rien...

[ju_bicycle]

Si c'est pour dire "j'ai la solution mais je ne dirait rien nananere..." je vois pas l'interet de ton post

[arnaudk]

Il faut aussi lire le début de son post, il donne une indication, et il me semble que le but du défi, c'est de le réaliser seul, non ?

[rambc]

Attention je ne demande surtout pas du code, mais plutot la logique derrière...Si quelqu'un a une idée...

Si je te donne la formule, il n'y a rien à faire car elle est toute simple. De plus, je pense que l'on peut calculer ce nombre de combinaisons sans passer par la formule.

Le sens de mon post n'est pas dans l'esprit de ta remarque. Sur ce, je ne répondrais plus à tes messages si tu le prends sur ce ton.

[ju_bicycle]

Effectivement la formule ne m'interessait pas. Pour ma précédente réponse, reconnait que:

Dans ce cas, les mathématiques ont une réponse mais là je ne dirais rien...

Fait un peu du "nananere". Rien de bien méchant, c'est une remarque c'est tout

Ceci dit l'indication du +1/-1 m'a donné le coup de pouce necessaire. Donc je t'en remercie. Mais en fait c'est meme un peu plus simple puisqu' apparemment
d'aprés l'exemple fournit on ne peut pas revenir en arriere.Donc uniquement des +1 (en x ou en y)...

[rambc]

Fait un peu du "nananere".

J'ai juste passé l'âge de ce genre de niaiserie. Voici un fichier commenté sur le problème 15. Il fonctionne avec Python 3.

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#!/usr/bin/env python
#
# WARNNG : use Python 3
#
# This code solves brutally the following problem (cf. http://projecteuler.net/index.php?section=problems&id=15) :
#    Starting in the top left corner of a 2*2 grid, there are 6 routes (without backtracking) to the bottom right corner.
#    How many routes are there through a 20*20 grid?
#
# Nous devons modéliser un chemin comme le suivant pour une grile 3*3
# (on change la dimension par rapport à celle du problème car on s'intéresse
# aux intersections de la grille et non à son nombre de carreaux) :
#
#    S | . | .
#    * | * | .
#    . | * | E
#
# Nous avons à chaque étape deux alternatives, où on note (x;y) les coorodnnées dans la grille :
#    1) Soit on se déplace horizontalement d'une case : x += 1.
#    2) Soit on se déplace verticalement d'une case : y += 1.
#
# Nous avons deux contraintes :
#    1) Quand x = 4 (pour une grille 4*4), on ne peut plus faire que y += 1 jusqu'à obtenir y = 4.
#    2) Quand y = 4 (pour une grille 4*4), on ne peut plus faire que x += 1 jusqu'à obtenir x = 4.
#
# Voici une modélisation possible du chemin représenté ci-dessus en exemple :
#    0-1-0-1
# Ce codage ce lit comme suit : au départ on ne bouge pas horizontalement,
# donc on monte de un, puis ensuite on bouge horizontalment de un
# donc on ne bouge pas verticalement.. etc.
#
# Tous les chemins possibles sont modélisés comme suit :
#
#    0-0-1-1
#    0-1-0-1
#    0-1-1-0
#    1-0-0-1
#    1-0-1-0
#    1-1-0-0
#
# On constate donc que l'on doit avoir à chaque fois deux 0 et deux 1.
# Ceci donne la voix pour la solution mathématique mais c'est pour après.
#
# Passons maintenant au programme brutal dans le cas connu.
 
nbreChemins = 0
tailleGrille = 3
 
for rangPremierZero in range(tailleGrille):
    for rangSecondZero in range(rangPremierZero+1, tailleGrille+1):
        nbreChemins += 1
 
print('')
print('Pour une grille de taille {0}, il existe {1} chemins possibles.'.format(tailleGrille, nbreChemins))
 
# Comment généraliser cela. Et bien comme suit...
 
# Voici une grille 5*5 (toujours avec notre convention), et une autre 6*6 :
#
#    S | * | * | * | *                  S | * | * | * | * | *
#    . | . | . | . | *                  . | . | . | . | . | *
#    . | . | . | . | *                  . | . | . | . | . | *
#    . | . | . | . | *                  . | . | . | . | . | *
#    . | . | . | . | E                  . | . | . | . | . | *
#                                       . | . | . | . | . | E
#
# Notre modélisation est de longeur 8 pour la grille 5*5, et 12 pour la grille 6*6.
# Il suffit de considérer le chemin particulier indiqué.
#
# Ceci nous amène à la formule suivante : pour une grille N*N, notre modélistaion sera de longueur 2(N-1).
# On constate aussi que le nombre de zéros doit être égal à (N-1)
#
# Voilà ou cela nous mène.
 
tailleGrille = 3
 
nbreDeZeros = tailleGrille -1
# Remarque : nbreMaxDeplacements = 2*nbreDeZeros
 
# Il faut remplacer les boucles imbriquées suivantes :
#
#    for rangPremierZero in range(nbreDeZeros):
#        for rangSecondZero in range(rangPremierZero, nbreDeZeros+1):
#            for rangTroisiemeZero in range(rangTroisiemeZero, nbreDeZeros+2):
#                    ... etc
 
def monCompteur(nbreDeZeros, indiceDuZeroActuel, debutBoucle):
    nbreChemins = 0
    iMax = nbreDeZeros + indiceDuZeroActuel + 1
 
    if indiceDuZeroActuel == nbreDeZeros -1:
        for i in range(debutBoucle, iMax):
            nbreChemins += 1
    else:
        for i in range(debutBoucle, iMax):
            nbreChemins += monCompteur(nbreDeZeros, indiceDuZeroActuel + 1, i+1)
 
    return nbreChemins
 
nbreChemins = monCompteur(nbreDeZeros, 0, 0)
 
 
print('')
print('Pour une grille de taille {0}, il existe {1} chemins possibles.'.format(tailleGrille, nbreChemins))
 
# Pour finir, voici la solution mathématique :
#
# Considérons une grille 6*6 pour fixer les idées :
#
#    S | * | * | * | * | *
#    . | . | . | . | . | *
#    . | . | . | . | . | *
#    . | . | . | . | . | *
#    . | . | . | . | . | *
#    . | . | . | . | . | E
 
# Les chemins sont modélisés comme suit :
#
#    0-0-0-0-0-1-1-1-1-1
#    0-0-0-0-1-0-1-1-1-1
#    0-0-0-1-0-0-1-1-1-1
#    ... etc
#
# Choisir un chemin c'est choisir quatre emplacements pour les zéros parmi les huit possibles.
# Les mathématiques nous donnent que ce nombre est est égal au nombre de combinaisons de 4 parmi 8 :
#    8! / 4!^2
# Dans le cas général, pour une grille N*N avec notre convention, on a (2N-2)! / (N-1)!^2 chemins possibles.
#
# Testons les deux approches.
 
def combin(k,n):
    """Calcul de C(k;n) = n! / k!(n-k)! en utilisant
        C(k;n) = C(k-1;n-1) + C(k;n-1)"""
    if k==0 or k==n:
        return 1
 
    return (combin(k-1, n-1) + combin(k, n-1))
 
tests = [3, 6, 21]
 
for tailleGrille in tests:
    print('-'*30)
    print('tailleGrille = ' + str(tailleGrille))
 
    nbreDeZeros = tailleGrille -1
    nbreCheminsViaMath = combin(nbreDeZeros, 2*nbreDeZeros)
    print ('---' + str(nbreCheminsViaMath))
    nbreChemins = monCompteur(nbreDeZeros, 0, 0)
    print('...')
 
    if nbreChemins != nbreCheminsViaMath:
        print ('\tECHEC')
    else:
        print ('\tOK ! On obtient {0} chemins possibles;'.format(nbreChemins))

Il faut pas mal de temps pour la cas du problème 15 même via les combinaisons.