Voir le flux RSS

danielhagnoul

Python. PGCD de n nombres entiers

Noter ce billet
par , 23/11/2019 à 10h54 (644 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

Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Viadeo Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Twitter Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Google Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Facebook Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Digg Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Delicious Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog MySpace Envoyer le billet « Python. PGCD de n nombres entiers » dans le blog Yahoo

Tags: entier, list, min, pgcd, range
Catégories
Programmation , Python , Python

Commentaires

  1. Avatar de bistouille
    • |
    • permalink


    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
  2. Avatar de danielhagnoul
    • |
    • permalink
    La fonction diviseurs() était mon point de départ, mon besoin réel. La recherche du PGCD de plusieurs nombres est venue en bonus.