Comment décomposer un entier en produit de facteurs premiers ?

En utilisant le crible d'Ératosthène pour lister les premiers jusqu'à $\lfloor\sqrt{n}\rfloor$ , puis en divisant $n$ par ces premiers

L'objectif

Décomposer $n$ en facteurs premiers en s'aidant du crible d'Ératosthène pour disposer de la liste des premiers candidats.

Le principe

Si $n$ a un facteur premier $p$ , alors $p \leq \sqrt{n}$ (sauf si $n$ est lui-même premier) ; le crible donne tous les premiers jusqu'à $\lfloor\sqrt{n}\rfloor$ .

La méthode

1
Calculer $\lfloor\sqrt{n}\rfloor$ et dresser la liste $\{2, 3, \ldots, \lfloor\sqrt{n}\rfloor\}$ . Appliquer le crible d'Ératosthène : barrer les multiples de chaque premier $p$ à partir de $p^2$ .
2
Diviser $n$ par chaque premier $p$ de la liste (dans l'ordre croissant) autant de fois que possible, en tenant à jour le quotient.
3
Si le quotient final est $> 1$ après épuisement de la liste, ce quotient est un facteur premier de $n$ (supérieur à $\lfloor\sqrt{n}\rfloor$ ).
4
Écrire la décomposition complète de $n$ .

Exemple corrigé

Difficulté croissante de 1 à 5

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

En utilisant le crible d'Ératosthène pour lister les premiers jusqu'à ⌊n⌋\lfloor\sqrt{n}\rfloor⌊n​⌋, puis en divisant nnn par ces premiers

Exemple corrigé

En utilisant le crible d'Ératosthène pour lister les premiers jusqu'à $\lfloor\sqrt{n}\rfloor$ , puis en divisant $n$ par ces premiers