Plus grand facteur commun

Résolu
Vosda - 22 juil. 2021 à 02:50
brucine Messages postés 20243 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 17 mai 2025 - 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

Réponse 1 / 2
Utilisateur anonyme
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.
1
Vosda
Modifié le 22 juil. 2021 à 16:58
J'irais me renseigner sur cela, merci de votre réponse.
0
brucine Messages postés 20243 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 17 mai 2025 3 180 > 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
Réponse 2 / 2
brucine Messages postés 20243 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 17 mai 2025 3 180
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
Vosda
22 juil. 2021 à 16:58
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

Discussions similaires

Décomposition facteur premier casio 35+ Ell
Ccmqusst -
Pierr10 -

8 réponses
Dimensions L x l x H : comment lire ces infos ?
Miss-Curieuse -
valou -

8 réponses
ALEXIA A BESOIN D'AIDE
ALEX -
espion3004 -

7 réponses
Facebook : qui choisi les suggestions d'amis ?
almazy -
Cowboye -

176 réponses
Qui sont les personnes dans mon ajout rapide de Snapchat ?
lobino68 -
m_manolo25 -

21 réponses