## lecon 13 arithmétique

##-1 diviseurs, nombres premiers, factorisation(s)

#liste des diviseurs positifs

def diviseurs(x):
    D=[]
    dor d in range(1, x+1) :
        if  x % d == 0:
            D.append(d)
    return D

# le mm en mieux

def diviseurs(x):
    D=[]
    d=1
    while ... :
        if x % d == 0 :
            D.append(d)
            D.append(x//d)
        d+= 1
    if d** 2 == x :
        D.append(d)
        return D

# Et pour les avoir dans l'ordre

def diviseurs(x):
    LesPetits = []
    LesGros = []
    d = 1
    while d** 2 < x :
        if x % d == 0:
            LesPetits.append(d)
            LesGros.append(x//d)
        d+= 1
    if d** 2 == x:
        LesPetits.append(d)
    while LesGros != []:
        LesPetits.append(Les.gros.pop())
    return LesPetits

# produit des diviseurs

def ProduitDesDiviseurs(x):
    D= diviseurs(x)
    P=1
    for d in D :
        P*= d
    return P

## Nombres premiers

def EstPremier(x) :
    if x< 2 :
        return False
    elif x % 2 == 0 :
        return x == 2
    else :
        d= 3
        while d**2 <= x :
            if x% d== 0:
                return False
            d+= 2
        return True


## Plus petit diviseur (à partir de main)

# On suppose que x n'a aucun diviseur strictement inférieur à dmin

def PlusPetitDiviseur(x, dmin) :
    d= dmin
    while d**2<= x:
        if x% d == 0:
            return d
        d+= 1
    return x

# liste des facteurs premiers (avec répétitions)
def FacteursPremiers(x):
    dmin = 2 ; F = []; x_ = x
    while x_ > 1 :
        p= PlusPetitDiviseur(x_, dmin)
        dmin = p ; F.append(p) ; x_ // =p
    return F

# valuation de p dans x : c'est le plus grand entier v tel que p**v divise x.

def Valuation(p,x):
    v= 0
    while x % p** (v + 1) ==0 :
        v += 1
    return v

# variante plus efficace

def Valuation(p, x):
    v= 0; x_=x
    while x_% p == 0 :
        v+= 1 , x_ //= p
    return v

# factorisation sous forme compacte
def Facttorisation(x):
    dmin = 2 ; F = [] ; x_ = x
    while x_ > 1:
        p = PlusPetitDiviseur(x_, dmin)
        v = Valuation(p,x_)
        dmin = p + 1 ; F.append( (p,v)) ;x_//=p **v
    return F

## tous les nb premiers: le crible d'érathostène

"""
on construit une liste B de booléens, indicée de 0 jusqu'à M, et on fait en sorte que la case B[x] soit vraie si et seulement si x est prmier .
"""

def erathosthène(M):
    B=[True]*(M+1)
    B[0] = False ; B[1] = False
    d= 2
    while d**2 <= M:
        m = d*2
        while  m<M :
            B[m] = False
            m+= d
        d+= 1
        while d**2 <= M and not B[d] :
            d+= 1
    P= []
    for x in range(0, M+1):
        if B[x]:
            P.append(x)

    return P

## 2 - L'algo d'Euclide

def PGCD(x, y):
    x_= abs(x) ;y_=abs(y)
    while y_> 0:
        (x_, y_)=(y_, x_ % )