Différences

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

--- teaching:progappchim:algos_entiers [2015/04/14 15:20] – [Factorisation en nombres premiers] villersd
+++ teaching:progappchim:algos_entiers [2015/04/20 08:29] – villersd
@@ Ligne 97: / Ligne 97: @@
   * [[http://gumuz.nl/weblog/python-extended-slice-assignment/|Explication de l'affectation multiple via des slices]]
 ===== Factorisation en nombres premiers =====
+Version élémentaires, par essais systématiques de diviseurs :
+<sxh python; title : factorisation_nombres_premiers-01.py>
+#!/usr/bin/env python
+# -*- coding: UTF-8 -*-
+"""
+Factorisation en nombres premiers ; méthode par essais successifs
+"""
+def prime_factors(n):
+    li = []
+    f = 2  # premier facteur à tester
+    while f*f <= n:
+        while (n % f) == 0:
+            li.append(f)  # on ajoute f à la liste
+            n = n/f           # on divise par f
+        f = f+1 if f == 2 else f+2  # pour ne pas essayer les nombres pairs
+    if n > 1:  # si on n'a pas obtenu n=1, alors le facteur restant est premier
+       li.append(n)
+    return li
+p=prime_factors(1234567890)
+print p
+</sxh>
+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 =====
   * [[http://stackoverflow.com/questions/16996217/prime-factorization-list]]
@@ Ligne 108: / 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  (//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 :
+^ 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 =====