Pular para conteúdo

MDC

mdc(a, b)

MDC utilizando algoritmo de euclides, onde MDC(a,b) = MDC(b,r), sendo 'r' o resto da divisão de a por b

Attributes:

Name Type Description
a int

O primeiro inteiro que será utilizado para o cálculo do MDC
b int

O segundo inteiro que será utilizado para o cálculo do MDC

Returns:

Type Description
int

O Máximo Divisor Comum entre 'a' e 'b'

Examples:

>>> mdc(12, 4)
4

>>> mdc(5, 9)
1
Source code in rsa/utils/MDC.py 
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
def mdc(a: int, b: int):
    """
    MDC utilizando algoritmo de euclides, onde MDC(a,b) = MDC(b,r),
    sendo 'r' o resto da divisão de a por b

    Attributes:
        a (int): O primeiro inteiro que será utilizado para o cálculo do MDC
        b (int): O segundo inteiro que será utilizado para o cálculo do MDC

    Returns:
        (int): O Máximo Divisor Comum entre 'a' e 'b'

    Examples:
        >>> mdc(12, 4)
        4

        >>> mdc(5, 9)
        1
    """
    if b > a:
        a, b = b, a

    # O objetivo é que esta condição seja atingida para que termine a recursividade
    if b == 0:
        return a
    r = a % b
    return mdc(a=b, b=r)