Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

Factoriser de gros nombres ?

Posté par
Al-Allo
23-08-12 à 21:31

Salut, j'aurai une petite question simple.

Comment est-ce que l'on factorise de gros nombres? Existe-t-il une certaine technique à connaître ? Exemple : 2016

Je suis supposé faire un arbre des facteurs avec ce nombre...Comment commencer ?

PS: J'ai déjà les facteurs premiers de ce nombre...
Merci!

Posté par
pgeod
re : Factoriser de gros nombres ? 23-08-12 à 21:39

2016 est pair, donc divisible par 2
la somme des chiffres est divisible par 9, donc divisible par 9
etc...

Posté par
Al-Allo
re : Factoriser de gros nombres ? 23-08-12 à 21:43

Donc c'est essai erreur ?

Posté par
pgeod
re : Factoriser de gros nombres ? 23-08-12 à 21:49

Citation :
Donc c'est essai erreur ?

je ne capte pas. C'est écrit en quelle langue ?

Posté par
mathafou Moderateur
re : Factoriser de gros nombres ? 23-08-12 à 21:51

Bonjour,

je ne comprends pas :

Citation :
Comment est-ce que l'on factorise de gros nombres
J'ai déjà les facteurs premiers de ce nombre



bon, trève de plaisanterie.

La méthode "brutale" d'essayer tous les diviseurs potentiels (c'est à dire 2, puis 3, 5, puis tous les 6n (pourquoi ceux là seulement ?)
jusqu'à n est encore la plus efficace pour des petits
nombres (disons jusqu'à quelques milliers, voire par programme un peu plus loin)

Au dela il faut utiliser des techniques qui sont d'autant plus incompréhensibles au niveau Lycée qu'elles sont puissantes.
Courbes elliptiques, corps finis etc
Pour les très gros nombres (centaines de chiffres) on ne sait pas faire.
C'est là dessus que sont basées les méthodes de cryptographie : on sait faire théoriquement, mais cela prendrait un temps de calcul prohibitif.

Par contre ta question est en fait plutot comment faire l'arbre des facteurs connaissant les facteurs premiers ! non ?

Posté par
Al-Allo
re : Factoriser de gros nombres ? 23-08-12 à 21:52

Reformulation : Il faut essayer un par un chaque nombre pour voir si c'est divisible ou pas ?

Posté par
Al-Allo
re : Factoriser de gros nombres ? 23-08-12 à 21:54

Oui, ça serait cela. ^^

J'ai mal formulé ma question! Merci de l'aide.

Posté par
pgeod
re : Factoriser de gros nombres ? 23-08-12 à 22:01

On ne peut pas dire que 2016 soit un gros nombre !

Si on cherche les facteurs premiers de ce nombre,
on utilise déjà les critères de divisibilité connus :

2016 divisible par 2 : 2 * 1008
1008 divisible par 2 : 2 * 2 * 504
504 divisible par 2 : 2 * 2 * 2 * 252
252 divisible par 2 : 2 * 2 * 2 * 2 * 126
126 divisible par 2 : 2 * 2 * 2 * 2 * 2 * 63
63  divisible par 9 : 2 * 2 * 2 * 2 * 2 * 3² * 7

Posté par
mathafou Moderateur
re : Factoriser de gros nombres ? 23-08-12 à 22:10

2016 = 25×32×7

en fait tu as un certain nombre de boites avec des billes dedans
1ere boite (le facteur premier 2) contient 5 billes rouges (25)
2ème boite (le facteur pemier 3) contient 2 billes vertes (32)
3ème boite (le facteur premier 7) contient une seule bille bleue

ce que tu cherches c'est toutes les façons possibles de faire un paquet de billes avec ça
Tu peux donc prendre 0, 1, ... ou 5 billes rouges pour faire ton tas
et 0, 1 ou 2 billes vertes
et 0 ou 1 bille bleue

déja tu as le nombre de possibilités de faire ton tas de billes (un diviseur) qui est donc 632 = 36
Là dedans tu as compté le diviseur 1 (aucune bille) et le diviseur 2016 lui-même (toutes les billes)
comme ne prendre aucune bille est "peu intéressant" (1 divise tous les nombres) considérer ce cas peut être exclus et on considère les "diviseurs propres" de 2016 comme ceux > 1 ( les 35 cas restants)

Générer une liste de tous ces diviseurs, c'est générer successivement tous ces tas de billes possibles
donc des boucles imbriquées
Pour i = 0..5
pour j = 0..2
pour k = 0..1
le diviseur est 2i3j7k
(on peut rejeter au besoin le diviseur 1 c'est à dire le cas i=j=k=0)

traduire cela en un arbre n'est alors qu'une formalité

En espérant que cela réponde à ta question.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !