#############################################
# PROGRAMMES DU PROBLEME DE LA SEMAINE 9
#############################################

# Test de primalité

def Tprem_ou_pas(n):
    assert n > 1
    TPREM = True
    d = 2
    while (d  < n) and (TPREM == True):
        if n % d == 0:
            TPREM = False
        d = d + 1
    return TPREM

# Valuation p-adique

def Vadic(n,p):
    assert n > 0
    assert Tprem_ou_pas(p)
    val = 0
    while n % (p**(val+1)) == 0:
        val += 1
    return val

# Fonction "Carmichael"

def Carmi(n):
    TCARMI = True
    if Tprem_ou_pas(n) == True:
        TCARMI = False
    k = 2
    while (k < n) and (TCARMI == True):
        if (k**n - k) % n != 0:
            TCARMI = False
        k = k + 1
    return TCARMI

# Liste des nombres de Carmichael entre a et b

def List_Carmi(a,b):
    L = []
    for k in range(a,b):
        if Carmi_ou_pas(k):
            L += [k]
    return L

# Liste des nombres de Carmichael entre a et b, avec affichage de la durée

from time import * # le module time contient la fonction time(), qui renvoie l'heure de l'horloge du système, en secondes. On peut s'en servir comme d'un chronomètre, comme l'illustre la fonction ci-dessous.

def List_Carmi2(a,b):
    t0 = time() # On déclenche le chronomètre
    L = List_Carmi(a,b)
    duree = int(1000 * (time() - t0)) / 1000 # On arrête le chrono, et on calcule la durée (avec 3 décimales)
    return L, duree