Plus grand facteur commun

Résolu/Fermé
Vosda - 22 juil. 2021 à 02:50
brucine Messages postés 7474 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 6 décembre 2022 - 22 juil. 2021 à 17:11
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

Whismeril Messages postés 18024 Date d'inscription mardi 11 mars 2003 Statut Contributeur Dernière intervention 6 décembre 2022 876
Modifié le 22 juil. 2021 à 06:48
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
1
J'irais me renseigner sur cela, merci de votre réponse.
0
brucine Messages postés 7474 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 6 décembre 2022 777 > Vosda
22 juil. 2021 à 17:11
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
0
brucine Messages postés 7474 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 6 décembre 2022 777
22 juil. 2021 à 08:26
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.
1
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.
0