fakbill a écrit :Outch ce thread en dit long sur les connaissances de base de chez de base en algo du taupin moyen

Je sais bien qu'on ne peut pas tout faire mais il serait tout de même bon de dire que la décomposition en facteurs premiers est un algo "très gourmand en temps" (on peut juste s'en tenir à cette vague remarque) et que donc, en pratique, on ne décompose en facteurs premiers que sous la torture.
Là n'est pas la question. Il s'agit d'avoir en revue des méthodes c'est tout. Si leur prof leur a demandé de le faire sans qu'ils aient vu avec l'algorithme d'Euclide, c'est légitime, ça leur permet de chercher une autre méthode : aucune manière de faire est à négligée, on demande bien de démontrer des résultats d'algèbre sans passer par des théorèmes "puissants" de réduction par exemple, ne serait-ce que pour former l'esprit à voir les différentes méthode pour accéder au même résultat. C'est toujours formateur.
on ne décompose en facteurs premiers que sous la torture
Il n'y a pas de meilleure méthode, ou de solution unique en maths. Il se peut que dans un énoncé on définissent un ensemble d'entiers, de telle manière a ce qu'il soit impossible de calculer leur pgcd avec l'algorithme d'Euclide, mais en passant par leur décomposition en facteurs premiers.
Maintenant répéter que c'est gourmand en temps alors que ça a été dit à je ne sais combien de reprise : c'est évident que c'est couteux, dans ce cas bien précis, pour peu que l'on réfléchisse 3 secondes
