Plus grand facteur commun

[Résolu]
Signaler
-
Messages postés
781
Date d'inscription
lundi 22 février 2021
Statut
Membre
Dernière intervention
31 juillet 2021
-
Bonjour,

J'ai récemment fait un challenge en python consistant à trouver le plus grand facteur commun des élément dans un liste.
Cependant, je me suis souvenu d'une technique et j'ai fait une boucle qui ne s'arrête que lorsqu'elle a atteint la racine carrée du plus grand nombre de cette liste. Tous les tests visant à tester la validité de ma fonction on tous fonctionné, à ma plus grande surprise.

Je me demandais donc s'il existait bel et bien un théorème ou autre(ou tout simplement un algorithme plus performant), disant que le plus grand facteur commun d'un ensemble de nombre se trouve forcément entre 1 et la racine carrée du plus grand?
Quelqu'un m'avais suggéré de comparer la racine carrée du plus grand nombre et le plus petit nombre de l'ensemble et de définir comme limite de ma boucle le plus petit des deux. Dans le cas ou la racine serait plus grande, cela permettrait de gagner du temps.

Désolé de m'être un peu étendu... merci d'avance.

2 réponses

Messages postés
16132
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
31 juillet 2021
724
Bonjour

40, 60 et 100 ont tous 20 en diviseur commun qui est plus grand que 10 la racine de 100.

A moins que tu ne parles de décomposition en facteurs premiers.
Quand j'étais petit, la mer Morte n'était que malade.
George Burns
J'irais me renseigner sur cela, merci de votre réponse.
Messages postés
781
Date d'inscription
lundi 22 février 2021
Statut
Membre
Dernière intervention
31 juillet 2021
48 > Vosda
On trouve par exemple ici un récapitulatif des différentes méthodes de calcul, après, c'est effectivement à toi qu'il appartient "d'écrire" ça en Python:
https://www.dcode.fr/pgcd
Messages postés
781
Date d'inscription
lundi 22 février 2021
Statut
Membre
Dernière intervention
31 juillet 2021
48
Bonjour,

D'une part on parle plus volontiers de plus grand commun diviseur (PGCD) que de plus grand facteur commun.

D'autre part le fait que l'on utilise l'algorithme d'Euclide, la décomposition en nombres premiers ou une autre méthode ne change rien à la question.

Je ne sais pas dans quelle mesure il faut tenter de réinventer la roue, puisque internet regorge de calculs appliqués à tel modèle de calculatrice ou à tel langage de programmation, et qui eux sont validés.
Le challenge me demandait les plus grands facteurs communs mais la technique est la même en effet. Il semblerait que l'auteur du challenge n'ait pas pris en compte certaines valeurs si j'ai passé tous les tests. En pratique je me renseignerait sur les algorithmes existants comme vous me l'avez conseillé, mais en ce qui concerne les challenges, il était plus préférable d'arriver à une solution de moi-même.

Merci d'avoir répondu.