je souhaiterai avoir votre avis sur mon impl=C3=A9mentation du crible
d'Erastoth=C3=A8ne.
Mon code met 9 minute pour fournir la liste des nombres premier sur
l'intervalle [2, 10 000 000]
voici le lien du source : http://codepad.org/5CXy0oLS
sur l'intervalle [2, 120] celui-ci semble correct.
mon algo est-il bon ?
Le code, au niveau de la vitesse de calcul peut il =C3=AAtre am=C3=A9lior=
=C3=A9 ?
Vaut il mieux pour cr=C3=A9er un second vector nombres_premier o=C3=B9 sto=
cker
les nombres premier trouv=C3=A9 pour effectuer les divers traitements
possible sur un vector de taille forcement moindre ?
Comment puis-je mesurer ce genre de probl=C3=A8matique, sur un plan
efficacit=C3=A9 ?
je souhaiterai avoir votre avis sur mon implémentation du crible d'Erastothène.
Mon code met 9 minute pour fournir la liste des nombres premier sur l'intervalle [2, 10 000 000]
voici le lien du source : http://codepad.org/5CXy0oLS
sur l'intervalle [2, 120] celui-ci semble correct.
mon algo est-il bon ? Le code, au niveau de la vitesse de calcul peut il être amélioré ?
Au niveau de la vitesse de calcul, tu pourrais ramener les doigts dans le nez, en utilisant un compilateur lisp ciblant une machine virtuelle, (et en perdant un peu de temps dans un ramassage de miettes), à deux secondes et demi sur mon i7:
CL-USER> (time (defvar *primes* (COM.INFORMATIMAGO.COMMON-LISP.ARITHMETIC.PRIMES:COMPUTE-PRIMES-TO 10000000))) Real time: 2.53821 sec. Run time: 2.536615 sec. Space: 5942648 Bytes GC: 1, GC time: 0.010998 sec. *PRIMES* CL-USER>
(Bien sur, si j'utilisais un compilateur lisp générant du code natif bien optimisé, ça pourrait aller encore plus vite).
Vaut il mieux pour créer un second vector nombres_premier où stocker les nombres premier trouvé pour effectuer les divers traitements possible sur un vector de taille forcement moindre ?
Il vaut mieux programmer dans un langage de plus haut niveau. Ça laisse l'esprit plus libre pour trouver de meilleurs algorithmes.
Comment puis-je mesurer ce genre de problèmatique, sur un plan efficacité ?
En profilant. Voir gcov, gprof, etc.
Le principal problème dans ton code, c'est la ligne 43, qui incrémente j seulement de 1. Donc, après 3, tu vas chercher à éliminer les multiples de 4, or ils ont déjà été éliminés en tant que multiples de 2, etc.
Similairement, ligne 30, il n'y a aucune raison de cribler tous les entiers, puisque seuls les nombres supérieurs à j peuvent être un multiple de j.
En fin de compte tu n'as pas implémenté le crible d'Ératosthène, puisque ton algorithme consiste à diviser systématiquement tous les entiers par tous les entiers.
Fais une recherche google sur crible d'Ératosthène, et regarde les images ou les vidéo démontrant son fonctionnement. Par exemple, sur http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne Pour supprimer de la liste les multiples de p, on n'a pas besoin de diviser par p, il suffit de cocher bêtement une case sur p.
-- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}.
Olivier BURELLI <olivier@burelli.fr> writes:
je souhaiterai avoir votre avis sur mon implémentation du crible
d'Erastothène.
Mon code met 9 minute pour fournir la liste des nombres premier sur
l'intervalle [2, 10 000 000]
voici le lien du source : http://codepad.org/5CXy0oLS
sur l'intervalle [2, 120] celui-ci semble correct.
mon algo est-il bon ?
Le code, au niveau de la vitesse de calcul peut il être amélioré ?
Au niveau de la vitesse de calcul, tu pourrais ramener les doigts dans
le nez, en utilisant un compilateur lisp ciblant une machine virtuelle,
(et en perdant un peu de temps dans un ramassage de miettes), à deux
secondes et demi sur mon i7:
CL-USER> (time (defvar *primes* (COM.INFORMATIMAGO.COMMON-LISP.ARITHMETIC.PRIMES:COMPUTE-PRIMES-TO 10000000)))
Real time: 2.53821 sec.
Run time: 2.536615 sec.
Space: 5942648 Bytes
GC: 1, GC time: 0.010998 sec.
*PRIMES*
CL-USER>
(Bien sur, si j'utilisais un compilateur lisp générant du code natif
bien optimisé, ça pourrait aller encore plus vite).
Vaut il mieux pour créer un second vector nombres_premier où stocker
les nombres premier trouvé pour effectuer les divers traitements
possible sur un vector de taille forcement moindre ?
Il vaut mieux programmer dans un langage de plus haut niveau. Ça laisse
l'esprit plus libre pour trouver de meilleurs algorithmes.
Comment puis-je mesurer ce genre de problèmatique, sur un plan
efficacité ?
En profilant. Voir gcov, gprof, etc.
Le principal problème dans ton code, c'est la ligne 43, qui incrémente j
seulement de 1. Donc, après 3, tu vas chercher à éliminer les multiples
de 4, or ils ont déjà été éliminés en tant que multiples de 2, etc.
Similairement, ligne 30, il n'y a aucune raison de cribler tous les
entiers, puisque seuls les nombres supérieurs à j peuvent être un
multiple de j.
En fin de compte tu n'as pas implémenté le crible d'Ératosthène, puisque
ton algorithme consiste à diviser systématiquement tous les entiers par
tous les entiers.
Fais une recherche google sur crible d'Ératosthène, et regarde les
images ou les vidéo démontrant son fonctionnement. Par exemple, sur
http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne
Pour supprimer de la liste les multiples de p, on n'a pas besoin de
diviser par p, il suffit de cocher bêtement une case sur p.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
je souhaiterai avoir votre avis sur mon implémentation du crible d'Erastothène.
Mon code met 9 minute pour fournir la liste des nombres premier sur l'intervalle [2, 10 000 000]
voici le lien du source : http://codepad.org/5CXy0oLS
sur l'intervalle [2, 120] celui-ci semble correct.
mon algo est-il bon ? Le code, au niveau de la vitesse de calcul peut il être amélioré ?
Au niveau de la vitesse de calcul, tu pourrais ramener les doigts dans le nez, en utilisant un compilateur lisp ciblant une machine virtuelle, (et en perdant un peu de temps dans un ramassage de miettes), à deux secondes et demi sur mon i7:
CL-USER> (time (defvar *primes* (COM.INFORMATIMAGO.COMMON-LISP.ARITHMETIC.PRIMES:COMPUTE-PRIMES-TO 10000000))) Real time: 2.53821 sec. Run time: 2.536615 sec. Space: 5942648 Bytes GC: 1, GC time: 0.010998 sec. *PRIMES* CL-USER>
(Bien sur, si j'utilisais un compilateur lisp générant du code natif bien optimisé, ça pourrait aller encore plus vite).
Vaut il mieux pour créer un second vector nombres_premier où stocker les nombres premier trouvé pour effectuer les divers traitements possible sur un vector de taille forcement moindre ?
Il vaut mieux programmer dans un langage de plus haut niveau. Ça laisse l'esprit plus libre pour trouver de meilleurs algorithmes.
Comment puis-je mesurer ce genre de problèmatique, sur un plan efficacité ?
En profilant. Voir gcov, gprof, etc.
Le principal problème dans ton code, c'est la ligne 43, qui incrémente j seulement de 1. Donc, après 3, tu vas chercher à éliminer les multiples de 4, or ils ont déjà été éliminés en tant que multiples de 2, etc.
Similairement, ligne 30, il n'y a aucune raison de cribler tous les entiers, puisque seuls les nombres supérieurs à j peuvent être un multiple de j.
En fin de compte tu n'as pas implémenté le crible d'Ératosthène, puisque ton algorithme consiste à diviser systématiquement tous les entiers par tous les entiers.
Fais une recherche google sur crible d'Ératosthène, et regarde les images ou les vidéo démontrant son fonctionnement. Par exemple, sur http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne Pour supprimer de la liste les multiples de p, on n'a pas besoin de diviser par p, il suffit de cocher bêtement une case sur p.
-- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}.
Fabien LE LEZ
On Sun, 03 Jul 2011 01:55:29 +0200, "Pascal J. Bourguignon" :
lisp
Oui, on sait, Lisp est mieux que tout le reste. Note toutefois que fr.comp.lang.c++ est un groupe dédié au C++.
On Sun, 03 Jul 2011 01:55:29 +0200, "Pascal J. Bourguignon"
<pjb@informatimago.com>:
lisp
Oui, on sait, Lisp est mieux que tout le reste.
Note toutefois que fr.comp.lang.c++ est un groupe dédié au C++.
On Sun, 03 Jul 2011 01:55:29 +0200, "Pascal J. Bourguignon" :
lisp
Oui, on sait, Lisp est mieux que tout le reste. Note toutefois que fr.comp.lang.c++ est un groupe dédié au C++.
Fabien LE LEZ
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI :
je souhaiterai avoir votre avis sur mon implémentation du crible d'Erastothène.
La deuxième partie du message de Pascal est pertinente.
Le principe du crible : tous les nombres de 2 à N sont considérés comme premiers, et on enlève l'indicateur "premier" à une bonne partie des nombres, au fur et à mesure du crible.
À priori, le conteneur adéquat serait donc un vector<bool>, contenant au départ N fois "true" (sauf pour 0 et 1), et passage à "false" pour tous les multiples.
La boucle (version "naïve") :
vector<bool> v (N, true);
n=2 v[2]==true => 2 est un nombre premier. On peut l'afficher immédiatement. On enlève tous les multiples : v[4]= false; v[6]= false; etc.
n=3 v[3]==true => 3 est un nombre premier. On l'affiche, et on enlève tous les multiples.
n=4 v[4]=úlse => 4 n'est pas premier. On passe.
etc.
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI
<olivier@burelli.fr>:
je souhaiterai avoir votre avis sur mon implémentation du crible
d'Erastothène.
La deuxième partie du message de Pascal est pertinente.
Le principe du crible : tous les nombres de 2 à N sont considérés
comme premiers, et on enlève l'indicateur "premier" à une bonne partie
des nombres, au fur et à mesure du crible.
À priori, le conteneur adéquat serait donc un vector<bool>, contenant
au départ N fois "true" (sauf pour 0 et 1), et passage à "false" pour
tous les multiples.
La boucle (version "naïve") :
vector<bool> v (N, true);
n=2
v[2]==true => 2 est un nombre premier. On peut l'afficher
immédiatement.
On enlève tous les multiples : v[4]= false; v[6]= false; etc.
n=3
v[3]==true => 3 est un nombre premier. On l'affiche, et on enlève tous
les multiples.
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI :
je souhaiterai avoir votre avis sur mon implémentation du crible d'Erastothène.
La deuxième partie du message de Pascal est pertinente.
Le principe du crible : tous les nombres de 2 à N sont considérés comme premiers, et on enlève l'indicateur "premier" à une bonne partie des nombres, au fur et à mesure du crible.
À priori, le conteneur adéquat serait donc un vector<bool>, contenant au départ N fois "true" (sauf pour 0 et 1), et passage à "false" pour tous les multiples.
La boucle (version "naïve") :
vector<bool> v (N, true);
n=2 v[2]==true => 2 est un nombre premier. On peut l'afficher immédiatement. On enlève tous les multiples : v[4]= false; v[6]= false; etc.
n=3 v[3]==true => 3 est un nombre premier. On l'affiche, et on enlève tous les multiples.
J'ai pris en compte vos remarques, et je pense que ce code correspond au crible d'Erastothène.
Ben non, toujours pas. Il n'y a pas de division dans un vrai crible d'erathosthene. Regarde ta boucle interieure, c'est du grand n'importe quoi. C'est pourtant pas dur d'ecrire quelque chose genre:
for(unsigned int i = 2 * j; i < entier.size(); i += j) entiers[i] = 0;
Accessoirement, tu n'as aucune garantie que ton compilo va determiner que sqrt(m) est une constante et l'optimiser. Il vaut mieux garder au chaud la partie entiere de sa valeur pour eviter tout souci, e.g., const unsigned int bound = sqrt(m)
In article <20110703110754.51e18e3f@daenerys.zolive.eu>,
Olivier BURELLI <olivier@burelli.fr> wrote:
J'ai pris en compte vos remarques, et je pense que ce code correspond
au crible d'Erastothène.
Ben non, toujours pas. Il n'y a pas de division dans un vrai crible
d'erathosthene. Regarde ta boucle interieure, c'est du grand n'importe
quoi. C'est pourtant pas dur d'ecrire quelque chose genre:
for(unsigned int i = 2 * j; i < entier.size(); i += j)
entiers[i] = 0;
Accessoirement, tu n'as aucune garantie que ton compilo va determiner que
sqrt(m) est une constante et l'optimiser. Il vaut mieux garder au chaud
la partie entiere de sa valeur pour eviter tout souci, e.g.,
const unsigned int bound = sqrt(m)
J'ai pris en compte vos remarques, et je pense que ce code correspond au crible d'Erastothène.
Ben non, toujours pas. Il n'y a pas de division dans un vrai crible d'erathosthene. Regarde ta boucle interieure, c'est du grand n'importe quoi. C'est pourtant pas dur d'ecrire quelque chose genre:
for(unsigned int i = 2 * j; i < entier.size(); i += j) entiers[i] = 0;
Accessoirement, tu n'as aucune garantie que ton compilo va determiner que sqrt(m) est une constante et l'optimiser. Il vaut mieux garder au chaud la partie entiere de sa valeur pour eviter tout souci, e.g., const unsigned int bound = sqrt(m)
Fabien LE LEZ
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI :
Huumm le code suivant réalise exactement la même chose non ?
Non.
Ton code tente la division de chaque i par chaque j. En gros, c'est l'implémentation naïve de la détection de nombres premiers.
Le crible saute automatiquement les non-premiers, et n'effectue que des multiplications. Grosso modo, si tu as une division dans ton code (ou un modulo, ce qui revient au même), il ne s'agit pas du crible.
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI
<olivier@burelli.fr>:
Huumm le code suivant réalise exactement la même chose non ?
Non.
Ton code tente la division de chaque i par chaque j. En gros, c'est
l'implémentation naïve de la détection de nombres premiers.
Le crible saute automatiquement les non-premiers, et n'effectue que
des multiplications.
Grosso modo, si tu as une division dans ton code (ou un modulo, ce qui
revient au même), il ne s'agit pas du crible.
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI :
Huumm le code suivant réalise exactement la même chose non ?
Non.
Ton code tente la division de chaque i par chaque j. En gros, c'est l'implémentation naïve de la détection de nombres premiers.
Le crible saute automatiquement les non-premiers, et n'effectue que des multiplications. Grosso modo, si tu as une division dans ton code (ou un modulo, ce qui revient au même), il ne s'agit pas du crible.
Pascal J. Bourguignon
Olivier BURELLI writes:
Huumm le code suivant réalise exactement la même chose non ?
// Crible // Partir du premier nombre premier
unsigned long int j=2;
// Iterer tant que le plus petit nombre premier trouvé // est inférieur a SQRT(borne maximale)
while (j < sqrt(m))
Nombre de boucles: sqrt(m) (à cause du j++)
// Parcourir le vector for (unsigned long int i=0; i < entiers.size(); ++i)
Nombre de boucles: sqrt(m)*entiers.size()
// ne pas éliminer la valeur j if (entiers[i] > j) {
Nombre de boucles: sqrt(m)*entiers.size() + nombre de tests: sqrt(m)*entiers.size()
// tester si l'entier est divisible. if (entiers[i] % j == 0)
Nombre total de boucles: sqrt(m)*entiers.size() + nombre total de tests: sqrt(m)*(2*entiers.size()-j) + nombre total de divisions: sqrt(m)*(entiers.size()-j)
entiers[i]=0; // Le marquer
(while (< cur-prime n)
;; nombre de boucles: nombre de premiers < n (voir ci-dessous)
(setq bit (+ cur-prime (/ (- cur-prime 3) 2)))
(while (< bit bits-max) (setf (aref bits bit) 0) (incf bit cur-prime) ;; Nombre de boucles (n - cur-prime)/cur-prime ;; nombre de tests: 0 (à part celui de la boucle) ;; nombre de divisions: 0 )
;; Ici on recherche le premier suivant O(next-prime - cur-prime) ;; ce qui fait que la boucle principale n'est exécutée qu'une fois pour ;; chaque premier. (setq bit (1+ (/ (- cur-prime 3) 2))) ;; search next prime (setq bit (position 1 bits :start bit)) (if bit (setq cur-prime (+ bit bit 3) prime-count (1+ prime-count)) (setq cur-prime n)))
Le nombre total de boucles interne sera donc p<n p<n Σ (n-p)/p = n Σ 1/p ≈ n log(n) p premier p premier
ce qui est bien moindre que n√n.
-- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}.
Olivier BURELLI <olivier@burelli.fr> writes:
Huumm le code suivant réalise exactement la même chose non ?
// Crible
// Partir du premier nombre premier
unsigned long int j=2;
// Iterer tant que le plus petit nombre premier trouvé
// est inférieur a SQRT(borne maximale)
while (j < sqrt(m))
Nombre de boucles: sqrt(m) (à cause du j++)
// Parcourir le vector
for (unsigned long int i=0; i < entiers.size(); ++i)
Nombre de boucles: sqrt(m)*entiers.size()
// ne pas éliminer la valeur j
if (entiers[i] > j)
{
Nombre de boucles: sqrt(m)*entiers.size()
+ nombre de tests: sqrt(m)*entiers.size()
// tester si l'entier est divisible.
if (entiers[i] % j == 0)
Nombre total de boucles: sqrt(m)*entiers.size()
+ nombre total de tests: sqrt(m)*(2*entiers.size()-j)
+ nombre total de divisions: sqrt(m)*(entiers.size()-j)
entiers[i]=0; // Le marquer
(while (< cur-prime n)
;; nombre de boucles: nombre de premiers < n (voir ci-dessous)
(setq bit (+ cur-prime (/ (- cur-prime 3) 2)))
(while (< bit bits-max)
(setf (aref bits bit) 0)
(incf bit cur-prime)
;; Nombre de boucles (n - cur-prime)/cur-prime
;; nombre de tests: 0 (à part celui de la boucle)
;; nombre de divisions: 0
)
;; Ici on recherche le premier suivant O(next-prime - cur-prime)
;; ce qui fait que la boucle principale n'est exécutée qu'une fois pour
;; chaque premier.
(setq bit (1+ (/ (- cur-prime 3) 2)))
;; search next prime
(setq bit (position 1 bits :start bit))
(if bit
(setq cur-prime (+ bit bit 3)
prime-count (1+ prime-count))
(setq cur-prime n)))
Le nombre total de boucles interne sera donc
p<n p<n
Σ (n-p)/p = n Σ 1/p ≈ n log(n)
p premier p premier
ce qui est bien moindre que n√n.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Huumm le code suivant réalise exactement la même chose non ?
// Crible // Partir du premier nombre premier
unsigned long int j=2;
// Iterer tant que le plus petit nombre premier trouvé // est inférieur a SQRT(borne maximale)
while (j < sqrt(m))
Nombre de boucles: sqrt(m) (à cause du j++)
// Parcourir le vector for (unsigned long int i=0; i < entiers.size(); ++i)
Nombre de boucles: sqrt(m)*entiers.size()
// ne pas éliminer la valeur j if (entiers[i] > j) {
Nombre de boucles: sqrt(m)*entiers.size() + nombre de tests: sqrt(m)*entiers.size()
// tester si l'entier est divisible. if (entiers[i] % j == 0)
Nombre total de boucles: sqrt(m)*entiers.size() + nombre total de tests: sqrt(m)*(2*entiers.size()-j) + nombre total de divisions: sqrt(m)*(entiers.size()-j)
entiers[i]=0; // Le marquer
(while (< cur-prime n)
;; nombre de boucles: nombre de premiers < n (voir ci-dessous)
(setq bit (+ cur-prime (/ (- cur-prime 3) 2)))
(while (< bit bits-max) (setf (aref bits bit) 0) (incf bit cur-prime) ;; Nombre de boucles (n - cur-prime)/cur-prime ;; nombre de tests: 0 (à part celui de la boucle) ;; nombre de divisions: 0 )
;; Ici on recherche le premier suivant O(next-prime - cur-prime) ;; ce qui fait que la boucle principale n'est exécutée qu'une fois pour ;; chaque premier. (setq bit (1+ (/ (- cur-prime 3) 2))) ;; search next prime (setq bit (position 1 bits :start bit)) (if bit (setq cur-prime (+ bit bit 3) prime-count (1+ prime-count)) (setq cur-prime n)))
Le nombre total de boucles interne sera donc p<n p<n Σ (n-p)/p = n Σ 1/p ≈ n log(n) p premier p premier
ce qui est bien moindre que n√n.
-- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}.
Fabien LE LEZ
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI :
Mon code met 9 minute pour fournir la liste des nombres premier sur l'intervalle [2, 10 000 000]
Pour référence : Je viens d'implémenter un crible en quelques lignes. Sur un Core2 Duo 1,8 GHz, il met un peu moins d'une seconde pour calculer les nombres premiers jusqu'à dix millions, et onze secondes pour calculer les nombres premiers jsuqu'à cent millions.
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI
<olivier@burelli.fr>:
Mon code met 9 minute pour fournir la liste des nombres premier sur l'intervalle [2, 10 000 000]
Pour référence :
Je viens d'implémenter un crible en quelques lignes.
Sur un Core2 Duo 1,8 GHz, il met un peu moins d'une seconde pour
calculer les nombres premiers jusqu'à dix millions, et onze secondes
pour calculer les nombres premiers jsuqu'à cent millions.
On Sun, 3 Jul 2011 00:31:59 +0000, Olivier BURELLI :
Mon code met 9 minute pour fournir la liste des nombres premier sur l'intervalle [2, 10 000 000]
Pour référence : Je viens d'implémenter un crible en quelques lignes. Sur un Core2 Duo 1,8 GHz, il met un peu moins d'une seconde pour calculer les nombres premiers jusqu'à dix millions, et onze secondes pour calculer les nombres premiers jsuqu'à cent millions.
espie
In article , Fabien LE LEZ wrote:
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI :
Huumm le code suivant réalise exactement la même chose non ?
Non.
Ton code tente la division de chaque i par chaque j. En gros, c'est l'implémentation naïve de la détection de nombres premiers.
Le crible saute automatiquement les non-premiers, et n'effectue que des multiplications.
des additions... il n'y a meme pas de multiplication dans le crible d'erathosthene implemente correctement, ce qui est vachement interessant pour sa perf.
In article <dvg017dptkic4lvolea33i04ta4ks6j296@4ax.com>,
Fabien LE LEZ <usenet19@x.edulang.com> wrote:
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI
<olivier@burelli.fr>:
Huumm le code suivant réalise exactement la même chose non ?
Non.
Ton code tente la division de chaque i par chaque j. En gros, c'est
l'implémentation naïve de la détection de nombres premiers.
Le crible saute automatiquement les non-premiers, et n'effectue que
des multiplications.
des additions... il n'y a meme pas de multiplication dans le crible
d'erathosthene implemente correctement, ce qui est vachement interessant
pour sa perf.
On Sun, 3 Jul 2011 08:33:04 +0000, Olivier BURELLI :
Huumm le code suivant réalise exactement la même chose non ?
Non.
Ton code tente la division de chaque i par chaque j. En gros, c'est l'implémentation naïve de la détection de nombres premiers.
Le crible saute automatiquement les non-premiers, et n'effectue que des multiplications.
des additions... il n'y a meme pas de multiplication dans le crible d'erathosthene implemente correctement, ce qui est vachement interessant pour sa perf.
