Différences

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

--- teaching:progappchim:algos_entiers [2015/04/14 14:10] – villersd
+++ teaching:progappchim:algos_entiers [2015/04/14 16:04] – villersd
@@ Ligne 98: / Ligne 98: @@
 ===== 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]]
+  * [[http://en.wikipedia.org/wiki/Talk%3APrime_factorization_algorithm]] (récursif)
+  * [[http://rosettacode.org/wiki/Prime_decomposition#Python]] (avancé)
+  * [[http://codereview.stackexchange.com/questions/11317/prime-factorization-of-a-number]] (améliorable)
+  * [[http://stackoverflow.com/questions/4643647/fast-prime-factorization-module]] (intéressant)
+  * [[http://gilles.dubois10.free.fr/Nombres/Naturels/decomposition.html]]
+  * [[http://python.jpvweb.com/mesrecettespython/doku.php?id=decomposition_en_facteurs_premiers]] (améliorable)
+  * [[http://anh.cs.luc.edu/331/code/factoring.py]] (intéressant)
+  * [[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]]