Sujet Précédent Sujet Suivant

Plus grand facteur commun

Résolu/Fermé
Vosda - 22 juil. 2021 à 02:50
brucine Messages postés 14353 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 29 avril 2024 - 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
Whismeril Messages postés 19032 Date d'inscription mardi 11 mars 2003 Statut Contributeur Dernière intervention 28 avril 2024 931
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 14353 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 29 avril 2024 1 821 > 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 14353 Date d'inscription lundi 22 février 2021 Statut Membre Dernière intervention 29 avril 2024 1 821
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

Arnaque Le BonCoin / DHL : connaissez-vous cette arnaque ?
emma621 -
Orely -

444 réponses
quesque les amis commun veut dir ?
embeure -
ceciliaindia -

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

8 réponses
Arnaque DHL sur Facebook Marketplace
manath -
Bebeangela -

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

176 réponses