Quelques algorithmes rencontrés fréquemment

# Liste des diviseurs d'un nombre entier
def liste_diviseurs(nombre):
    liste = []
    for diviseur in range(1,nombre+1):
        if nombre % diviseur == 0:
            liste.append(diviseur)
    return liste

# Déterminer si un nombre est premier
def est_premier(nombre):
    for diviseur in range (2,nombre):
        if nombre % diviseur == 0:
            return False
    return True

def liste_nombres_premiers(min, max):
    liste = []
    for i in range(min, max+1):
        if est_premier(i):
            liste.append(i)
    return liste

NOMBRE1 = 758
NOMBRE2 = 306

# méthode 1 : méthode des diviseurs - trouver les diviseurs de deux nombres et trouver le plus grand parmi eux
def PGCD(nombre1, nombre2):
    L1 = []
    L2 = []
    for i in range(1,nombre1+1):
        if nombre1 % i == 0:
            L1.append(i)
    for j in range(1, nombre2+1):
        if nombre2 % j == 0:
            L2.append(j)

    compare = []
    for element in L1:
        if element in L2:
            compare.append(element)
    return max(compare)

print('Méthode 1 :', PGCD(NOMBRE1,NOMBRE2))

# méthode 2 : la plus simple et la plus courte : par division euclidienne (algorithme d'Euclide)
def PGCD_division_euclidienne(a,b):
    # exemple : pour 758 et 306
    # 758 % 306 = 146 | 306 % 146 = 14 | 146 % 14 = 6 | 14 % 6 = 2 | 6 % 2 = 0
    # Le dernier reste non nul est 2 
    r = a
    while r != 0:
        r = a % b
        a = b
        b = r
    return (a)

print('Méthode 2 :', PGCD_division_euclidienne(NOMBRE1,NOMBRE2))

# méthode 3 : avec la méthode proposée dans le module math
import math

print('Méthode 3 :', math.gcd(NOMBRE1,NOMBRE2))

def sont_premiers(nombre1, nombre2):
    if math.gcd(nombre1, nombre2) == 1:
        return True
    return False

print(sont_premiers(NOMBRE1, NOMBRE2))

# Recherche du maxmimum dans une liste
# NOTE : on peut aussi utiliser la fonction min(liste)
def minimum_liste (liste):
    minimum = liste[0]
    for element in liste:
        if element < minimum:
            minimum = element
    return minimum

# Recherche du maximum dans une liste
# NOTE : on peut aussi utiliser la fonction max(liste)
def maximum_liste(liste):
    maximum = liste[0]
    for element in liste:
        if element > maximum:
            maximum = element
    return maximum

# Echanger deux variables
# plus simple dans une liste, on utilisera : liste[i], liste[i+1] = liste[i+1], liste[i]

def echange(valeur1, valeur2):
    tmp = valeur1
    valeur1 = valeur2
    valeur2 = tmp
    return (valeur1,valeur2)

# La suite de Fibonacci se détermine de la façon suivante :
# u0 = 1  u1 = 1  u2 = u0 + u1  u3 = u2 + u1 ...
#                 le terme suivant est la somme des deux termes précédents

def suite_fibonacci(n):
    suite = []
    u0 = 0
    u1 = 1
    suite.append(u0)
    suite.append(u1)
    for i in range(n):
        terme_suivant = u0 + u1
        suite.append(terme_suivant)
        u0 = u1
        u1 = terme_suivant
    return suite

# Méthode 1
def factorielle(nombre):
    result = 1
    if nombre == 0 or nombre == 1:
        return 1
    else:
        for i in range(nombre, 1, -1):
            result = result * i
        return result

# Méthode 2 : de façon récursive
def factorielle_recursive(nombre):
    if nombre == 0 or nombre == 1:
        return 1
    else:
        return nombre * factorielle_recursive(nombre-1)