Discussion :

[barthelv]

Bonjour,

J'ai trouvé plusieurs façons de coder le PGCD de deux nombres sur le forum C++:

http://www.developpez.net/forums/vie...highlight=pgcd

Le problème est que moi je veux calculer le PGCD de plusieurs nombres et pas seulement de deux. Du coup, j'hésite sur la méthode à appliquer. Question complexité, je pense qu'il doit existerun algo meilleur que de prendre les PGCD de chaque combinaison, ce qui risque d'être fastidieux...

[barthelv]

Je viens de trouver cette formule, est-elle la plus optimisée, ou puis-je trouver mieux?

Le P.G.C.D. de trois entiers peut être calculé par :

pgcd (a,b,c) =pgcd(pgcd(a,b),c) = pgcd (a, pgcd (b, c))

[khayyam90]

une possibilité pour calculer le pgcd de plusieurs nombres est de faire comme quand on veut le calculer à la main : tu décomposes tous tes nombres en produit de facteurs premiers, le pgcd sera le produit de ce que tu trouveras en commun sur toutes tes décompositions.

[barthelv]

une possibilité pour calculer le pgcd de plusieurs nombres est de faire comme quand on veut le calculer à la main : tu décomposes tous tes nombres en produit de facteurs premiers, le pgcd sera le produit de ce que tu trouveras en commun sur toutes tes décompositions.

Je ne pense pas que cela soit optimisé...

[Selenite]

une possibilité pour calculer le pgcd de plusieurs nombres est de faire comme quand on veut le calculer à la main : tu décomposes tous tes nombres en produit de facteurs premiers, le pgcd sera le produit de ce que tu trouveras en commun sur toutes tes décompositions.

Je ne pense pas que cela soit optimisé...

C'est même la pire des méthodes...

Pour calculer, le PGCD, le meilleur rapport simplicité/efficacité est sans doute l'algorithme d'Euclide. Pour un calcul à la main, on préfèrera aussi cette méthode. ;-)

[victorracine]

SAlut,

Si c'est pour ton pobleme de signal, pense deja à retirer les valeurs boublonsGCD(a,a)=a
A+

[JHelp]

Petite idée, à voir si ca te convient.

tab : tableau des entiers dont on cherchent le pgcd
nb : nombe d'éléments du tableau
E(reel)->entier : partie entiére
sqrt(reel)->reel : racine carré

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
 
PGCD(tab, nb)
 | max <- E(sqrt(tab[0]) + 1;
 | Pour(i=1; i<nb; i++)
 |  |  | m <- E(sqrt(tab[i])) + 1
 |  | Si(max < m)
 |  |  | max = m
 |  | Fin-Si
 | Fin-Pour
 | rang <- 2
 | reponse <- 1
 | Tant-Que(rang <= max)
 |  | n <- 0
 |  | Pour(i=0; i<nb; i++)
 |  |  | Si(tab[i] MOD rang == 0)
 |  |  |  | n ++
 |  |  |  | tab[i] <- tab[i] DIV rang
 |  |  | Fin-Si
 |  | Fin-pour
 |  | Si(n == nb)
 |  |  | reponse <- reponse * rang
 |  |  | max <- max DIV E(sqrt(rang))
 |  | Sinon Si(n == 0)
 |  |  | rang ++
 |  | Sinon
 |  |  | max <- E(sqrt(tab[0]) + 1;
 |  |  | Pour(i=1; i<nb; i++)
 |  |  |  | m <- E(sqrt(tab[i])) + 1
 |  |  |  | Si(max < m)
 |  |  |  |  | max = m
 |  |  |  | Fin-Si 
 |  |  | Fin-Pour
 |  | Fin-Si
 | Fin-Tant-Que
 | Renvoie reponse
Fin

JHelp

[Trap D]

Salut
Je suis d'accord avec

Pour calculer, le PGCD, le meilleur rapport simplicité/efficacité est sans doute l'algorithme d'Euclide. Pour un calcul à la main, on préfèrera aussi cette méthode.

J'ajouterai qu'il peut être intéressant de commencer par les deux plus petits nombres.