from math import sqrt,floor
#algos Arithmétique

#Liste des diviseurs
#1
def liste_div(n):
    liste = []
    for k in range(1,n+1):
        if n%k==0:
            liste.append(k)
    return liste

def liste_div2(n):
    liste = []
    if n%int(sqrt(n))==0 and int(sqrt(n))!=1:
        liste.append(int(sqrt(n)))
    for k in range(1,floor(sqrt(n))+1):
        if n%k==0 and k!=sqrt(n):
            liste.append(k)
            liste.append(int(n/k))
    liste.sort()
    return liste

# génération des nombres premiers sous une certaine valeur
# if len(liste_div2(n) == 2: stocke

def liste_prem(n):
    prem=[]
    for k in range(2,n+1):
        if len(liste_div2(k)) ==2:
            prem.append(k)
    return prem

# diviseurs communs

def liste_div_comm(a,b):
    liste_a=liste_div2(a)
    liste_b=liste_div2(b)
    listecomm=[]
    for k in liste_a:
        if k in liste_b:
            listecomm.append(k)
    return listecomm

def pgcd(a,b):
    return liste_div_comm(a,b)[-1]

#Nombres de Mersenne

def test_Mers(n):
    liste=[]
    for k in range(2,n+1):
        M=2**k-1
        if len(liste_div2(M))==2:
            liste.append(k)
    return liste

#recherche pgcd par soustractions
#algo recursif

def pgcd_rec(a,b):
    if a<b:
        if a!=0:
            b=b-a
            return pgcd_rec(a,b)
        else:
            return(b)
    else:
        return pgcd_rec(b,a)

def pgcd_ant(a,b):
    if a<b:
        return pgcd_ant(a,b-a)
    elif b<a:
        return pgcd_ant(b,a-b)
    else:
        return a

def pgcd_cars(a,b):
    while a!=0:
        if b<a:
            a,b=b,a
        else:
            a,b=a,b-a
    return b

def pgcd_euclide(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def euclide_etendu(a,b):
    u1,v1,u2,v2=1,0,0,1
    while b!=0:
        q=a//b
        a,b,u1,v1,u2,v2=b,a%b,u2,v2,u1-q*u2,v1-q*v2
    return a,u1,v1