Factorisation première et diviseurs
Décomposer N en puissances de nombres premiers et compter les diviseurs
Factorisation première et diviseurs est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Décomposez N
Chaque entier supérieur à 1 est un produit unique de nombres premiers. Trouver cette décomposition, sa décomposition en facteurs premiers, permet de résoudre de nombreux problèmes de théorie des nombres. 🧩
L'idée de la division par essais
Extrayez le plus petit nombre premier qui divise n, divisez n par ce facteur, puis recommencez. Cette simple division par essais réduit progressivement n à 1.
Parcourez jusqu'à la racine
Testez les diviseurs i tant que i*i reste inférieur ou égal à n. Au-delà de la racine carrée, il peut rester au plus un facteur premier.
while i * i <= n:
...Extrayez chaque facteur
Tant que i divise n, continuez la division et enregistrez i. Vous obtenez ainsi la puissance complète de ce nombre premier avant de passer au suivant.
while n % i == 0:
factors.append(i)
n //= iLe facteur premier restant
Après la boucle, si n est encore supérieur à 1, il s'agit lui-même d'un facteur premier supérieur à la racine carrée. Ajoutez-le une fois.
if n > 1:
factors.append(n)La routine complète
En combinant ces étapes, vous obtenez une décomposition en O(sqrt n), qui renvoie chaque nombre premier avec sa multiplicité complète, dans l'ordre.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fRegroupez les puissances
Pour compter les diviseurs, vous avez besoin de chaque nombre premier avec son exposant, par exemple 2^3 plutôt que 2,2,2. Un compteur regroupe proprement les répétitions.
from collections import Counter
exp = Counter(factorize(n))La formule des diviseurs
Si n vaut p1^a fois p2^b, le nombre de diviseurs est égal à (a+1) fois (b+1). Chaque exposant offre un choix supplémentaire.
Compter les diviseurs
Multipliez un plus chaque exposant pour tous les nombres premiers. Vous obtenez ainsi le nombre total de diviseurs sans devoir les énumérer.
count = 1
for e in exp.values():
count *= (e + 1)Somme des diviseurs
Une formule associée additionne les diviseurs à l’aide de la série géométrique de chaque nombre premier. La connaître vous aidera à résoudre les problèmes sur les nombres parfaits et les suites aliquotes.
Accélérer avec un crible
Pour de nombreuses factorisations, précalculez le plus petit facteur premier de chaque nombre avec un crible. Chaque requête peut alors être factorisée en un nombre logarithmique d’étapes.
Vérification rapide
Appliquez la formule de comptage des diviseurs à un nombre concret.
Récapitulatif
Vous pouvez maintenant factoriser N par divisions successives en O(sqrt n), récupérer le facteur premier restant, regrouper les exposants et compter les diviseurs avec la formule du produit. ✅
Questions Fréquemment Posées
La leçon « Factorisation première et diviseurs » est-elle gratuite ?
Oui — le texte complet de « Factorisation première et diviseurs » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Factorisation première et diviseurs » ?
Décomposer N en puissances de nombres premiers et compter les diviseurs Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Factorisation première et diviseurs » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- GCD, LCM et algorithme d’Euclide
- Tester la primalité jusqu’à sqrt(n)
- Crible d’Ératosthène
- Factorisation première et diviseurs