Discussion :

[F. Rahl]

Je débute la programmation sous calculettes graphiques Texas Instrument. Je précise que je ne connais aucun langage de programmation, sinon les bases du TI basic (boucles, conditions, etc).

J'ai des difficultés à écrire :

Un programme qui décompose un nombre en facteurs premiers.
Un programme qui à un nombre N entré par l'utilisateur, propose de calculer le pgcd de N nombres, eux aussi définis par l'utilisateur évidemment.


Merci d'avance pour vos réponses.

PS : je n'ai pas le droit d'utiliser la fonction pgcd(x) de la calculette. Il me faut m'inspirer de l'algorithme d'Euclide (à partir duquel j'ai écrit un programme qui calcule le pgcd de deux nombres).

[F. Rahl]

J'ai trouvé pour le PGCD.... donc ne vous cassez pas la tête.
J'ai juste besoin d'aide maintenant pour la décomposition en facteurs premiers.

[Mac LAK]

Tu as plusieurs solutions à la décomposition en produits de facteurs premiers :

• Le Crible d'Ératosthène : pratique pour des petites valeurs, infernal dès que l'on arrive à des chiffres "grands" (supérieurs à un million, ça commence déjà à pédaler dans la semoule).
• Essais de division "bourrins" : tu cherches des diviseurs (quelconques), puis tu cherches les diviseurs des diviseurs. S'il n'en a pas, il est premier, et donc est un des facteurs premier du nombre initial. Sinon, ses propres facteurs premiers sont aussi une partie de ceux du nombre initial.
• Essais de division optimisés : en testant avec des nombres premiers "connus" pour les premiers (disons jusqu'à 1000, obtenus par exemple avec un Crible). Pour les suivants, tu obtiens un nombre "réduit" après avoir trouvé au moins un de ses facteurs premiers, sur lequel tu réappliques l'algorithme.
• Dans tous les cas, inutile d'aller au delà de la racine carrée du nombre initial (aucun de ses diviseurs ne peut dépasser cette valeur), ni de tester les diviseurs pairs (deux est le seul nombre premier pair, donc tu divises par deux tant que le nombre résultant est pair...).

Plus de détails sur cette page.

[F. Rahl]

Ok merci beaucoup, j'ai opté pour le test des divisions bourrins !