L'approche la plus simple pour décomposer un entier en produit de facteurs premiers est de tenter progressivement de le diviser par des nombres premiers qu'on essaye dans l'ordre croissant: 2, 3, 5, 7, 11, 13, ...
Tant qu'un nombre premier divise notre nombre, on continue avec ce nombre premier. Dès que ça ne marche plus, on passe au nombre premier suivant
Par exemple, si on prend le nombre 156
- on commence par essayer de le diviser par 2: c'est possible 156 = 2 x 78
- on met 2 de côté et on cherche à diviser 78 par des nombres premiers
- on essaye de diviser 78 par 2: c'est possible 78 = 2 * 39
- on met 2 de côté et on cherche à diviser 39 par des nombres premiers
- on essaye de diviser 39 par 2: ça ne marche pas parce que 39 n'est pas pair
- on essaye de diviser 39 par le premier suivant, c'est à dire 3: ça marche 39 = 3 x 13
- on met 3 de côté et comme 13 est un nombre premier on peut arrêter de cherche
Le résultat final nous donne 156 = 2 x 2 x 3 x 13
Pour faciliter la recherche, il y a des astuces à connaitre:
- Si le nombre est pair, il est divisible par 2. On peut continuer la division par 2 jusqu'à obtenir un nombre impair
- Si la somme des chiffres d'un nombre est divisible par 3, le nombre est divisible par 3: par exemple, pour 123, on a 1+2+3=6 qui est divisible par 3, 123 est divisible par 3
- Pour la division par 5, le nombre doit finir par 0 ou 5
