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/14 16:04] – 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>
+FIXME : amélioration utilisant un crible
 ===== Références =====
   * [[http://stackoverflow.com/questions/16996217/prime-factorization-list]]
@@ Ligne 108: / Ligne 137: @@
   * [[http://en.wikipedia.org/wiki/Wheel_factorization]]
 ===== Recherche du PPCM =====
+Explication de la relation entre pgcd et ppcm via les facteurs premiers des nombres !
+  * [http://fr.wikipedia.org/wiki/Plus_petit_commun_multiple]]