| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente |
| teaching:progappchim:algos_entiers [2018/11/13 10:19] – [Problème du sac à dos] villersd | teaching:progappchim:algos_entiers [2023/01/10 09:04] (Version actuelle) – villersd |
|---|
| * [[http://openclassrooms.com/forum/sujet/crible-d-eratosthene-87347]] | * [[http://openclassrooms.com/forum/sujet/crible-d-eratosthene-87347]] |
| * [[http://gumuz.nl/weblog/python-extended-slice-assignment/|Explication de l'affectation multiple via des slices]] | * [[http://gumuz.nl/weblog/python-extended-slice-assignment/|Explication de l'affectation multiple via des slices]] |
| | * [[wp>fr:Nombre_premier_tronquable|Nombre premier tronquable]] |
| | * [[https://www.geeksforgeeks.org/left-truncatable-prime/]] |
| | * [[https://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base#Python]] |
| | * [[https://tutorialspoint.dev/algorithm/mathematical-algorithms/left-truncatable-prime]] |
| ===== Factorisation en nombres premiers ===== | ===== Factorisation en nombres premiers ===== |
| |
| * 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 | * 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 |
| |
| | Techniques avancées : |
| | * [[wp>Integer_factorization|Integer factorization]] |
| | * [[https://stackoverflow.com/questions/4643647/fast-prime-factorization-module|Fast prime factorization module]] (stackoverflow) |
| | * librairie sympy → pip install sympy (ou conda install sympy) |
| | * Use the function sympy.ntheory.factorint : "Given a positive integer n, factorint(n) returns a dict containing the prime factors of n as keys and their respective multiplicities as values." For example: |
| | <code python> |
| | from sympy.ntheory import factorint |
| | factorint(10**20+1) → {73: 1, 5964848081: 1, 1676321: 1, 137: 1} |
| | </code> |
| |
| ===== Références ===== | ===== Références ===== |
| * [[http://anh.cs.luc.edu/331/code/factoring.py]] (intéressant) | * [[http://anh.cs.luc.edu/331/code/factoring.py]] (intéressant) |
| * [[http://en.wikipedia.org/wiki/Wheel_factorization]] | * [[http://en.wikipedia.org/wiki/Wheel_factorization]] |
| | * [[https://github.com/grinsted/teachprimes|Some code to for teaching primes]] (génération de figures pour enseigner les nombres premiers) |
| | |
| | |
| ===== Recherche du PPCM ===== | ===== 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) ! | 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) ! |