Différences

Ci-dessous, les différences entre deux révisions de la page.

--- teaching:progappchim:algos_entiers [2015/04/14 16:04] – villersd
+++ teaching:progappchim:algos_entiers [2015/04/20 08:29] – villersd
@@ Ligne 124: / Ligne 124: @@
 </sxh>
-FIXME : amélioration utilisant un crible
+Exercices :
+  * amélioration la recherche en combinant l'utilisation du crible d'Eratosthenes
+  * utiliser la décomposition en facteurs premiers de deux nombres (ou plus) pour trouver leur PGCD : pour l'ensemble des facteurs communs aux nombres, il s'agit du produit de ces facteurs élevés à la puissance la plus basse dans les décompositions
 ===== Références =====
@@ Ligne 137: / Ligne 140: @@
   * [[http://en.wikipedia.org/wiki/Wheel_factorization]]
 ===== Recherche du PPCM =====
-Explication de la relation entre pgcd et ppcm via les facteurs premiers des nombres !
+Explication de la relation entre PGCD et PPCM via les facteurs premiers des nombres  (//cf.// [[http://fr.wikipedia.org/wiki/Plus_petit_commun_multiple|wikipedia]]) : le PPCM de deux nombres est obtenu par le produit de chacun des facteurs premiers dans la décomposition des deux nombres, élevés à la puissance la plus haute dans ces décompositions. On a alors que le produit des deux nombres équivaut au produit du PGCD par le PPCM et dès lors : PPCM(a,b) = a * b / PGCD(a,b) !
+Voici un exemple utilisant les décompositions en facteur premier de 1470 et 252 :
-  * [http://fr.wikipedia.org/wiki/Plus_petit_commun_multiple]]
+^ Facteurs premiers de 1470 ^ Facteurs premiers de 252^
+| __2__ | **2<sup>2</sup>** |
+| __3__ | **3<sup>2</sup>**|
+| **5** | |
+| **7<sup>2</sup>** | __7__ |
+Le PGCD est 42, obtenu par le produit des facteurs communs (soulignés), tandis que le PPCM est obtenu par le produit de tous les facteurs, en utilisant la puissance la plus grande (en gras). Tous les facteurs du tableau de décomposition, soit de la première colonne, soit de la seconde, sont tous utilisés. Par conséquent on a bien pour deux nombres a et b que PPCM(a,b) = a * b / PGCD(a,b) !
 ===== Problème du sac à dos =====