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

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

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$ .

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Exemple 1 — $n = 35$

Étape 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

$\lfloor\sqrt{35}\rfloor = 5$ . Liste : $\{2,3,5\}$ . Crible : barrer $4,6,8,\ldots$ (multiples de $2$ ), $9,15,\ldots$ (multiples de $3$ ), $25$ (multiple de $5$ ). Premiers : $2, 3, 5$ .

Étape 2 —

Diviser

n

par chaque premier

p

de la liste (dans l'ordre croissant) autant de fois que possible, en tenant à jour le quotient.

$35$ n’est divisible ni par 2 ni par 3. On divise par 5 : $35 \div 5 = 7$ , facteur $5^1$ . Quotient = 7.

Étape 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

Liste épuisée. Quotient $= 7 > 1$ , donc $7$ est un facteur premier.

Étape 4 —

Écrire la décomposition complète de

n

$35 = 5 \times 7$ .

Application guidée

Exemple 2 — $n = 84$

Application autonome 1

Exemple 3 — $n = 210$

Application autonome 2

Exemple 4 — $n = 289$

Application autonome 3

Exemple 5 — $n = 1001$

Crée ton compte gratuit pour accéder à la fiche et aux exercices

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

Pour comprendre, fais des exercices !

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