danielhagnoul

Python. PGCD de n nombres entiers

par

, 23/11/2019 à 09h54 (2017 Affichages)

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#! python 3
# coding: utf-8
 
from termcolor import cprint
from typing import List
 
 
def diviseurs(a: int = 2, b: int = 2) -> List[int]:
    """Liste des diviseurs des nombres entiers a et b"""
    if a > 1 and b > 1:
        lst = []
        for n in range(min(a, b), 0, -1):
            if (a % n == 0) and (b % n == 0):
                lst.append(n)
        return lst
    else:
        raise Exception(
            'a et b doivent être des entiers supérieurs à 1')
 
 
def pgcd_n(int_list: List[int] = [40, 20]) -> int:
    """PGCD de 2..n nombres entiers supérieurs à 1"""
    if len(int_list) < 2:
        raise Exception('Il doit y avoir un minimum de deux nombres entiers')
    pgcd = 2
    while True:
        if len(int_list) >= 2 and pgcd > 1:
            a, b, *rest = int_list
            pgcd = diviseurs(a, b)[0]
            int_list = [pgcd, *rest]
        else:
            break
    return pgcd
 
 
# liste des diviseurs(2, 2)
# cprint(diviseurs(), 'green')  # [2, 1]
 
# liste des diviseurs(316, 24)
# cprint(diviseurs(316, 24), 'green') # [4, 2, 1]
 
# pgcd de n nombres [40, 20]
# cprint(pgcd_n(), 'cyan')  # 20
 
# pgcd de multiples de 53
cprint(pgcd_n([53*4, 53*8, 53*6]), 'red') # 106

Licence Creative Commons Attribution 2.0 Belgique

Tags: entier, list, min, pgcd, range

Catégories: Programmation , Python , Python

« Voir l'évolution des langages de programmation les plus populaires depuis 1965 Liste des billets Python. Intégrale d'une fonction par trois méthodes classiques »

Commentaires

bistouille - 08/12/2019 10h48

Encore de passage sur un de tes billets

Ce script est beaucoup trop lent, normal car tu calcules tous les diviseurs de chaque nombres, d'ailleurs la fonction diviseurs n'est pas du tout géniale.

J'ai fait un simple test avec de grands nombres comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
base = 53 * 47 * 19 * 1001
values = (base * 71, base * 109, base * 109 * 71)

Et ça mouline grave avec ta fonction pgcd_n

Alors qu'avec une fonction comme

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def pgcd(*values) :
    from itertools import combinations
    def _pgcd(a, b) :
        m = a % b
        while m :
            a, b = b, m
            m = a % b
        return b
    return min(_pgcd(a, b) for a, b in combinations(values, 2))

Le résultat est instantané.
Je n'ai rien inventé, cet algo est connu pour trouver rapidement le PGCD de 2 nombres

danielhagnoul - 08/12/2019 10h56
- |
La fonction diviseurs() était mon point de départ, mon besoin réel. La recherche du PGCD de plusieurs nombres est venue en bonus.