import math
from time import time


# =============================================
# Exercice 1 : Assertions
# =============================================

# 1. Test : t est un tuple
def test_tuple(t):
    assert isinstance(t, tuple), "t doit être un tuple"


# 2. Test : n est un entier non nul
def test_entier_non_nul(n):
    assert isinstance(n, int) and n != 0, "n doit être un entier non nul"


# 3. Exemple de fonction usuelle avec assert
def division(a, b):
    """Exemple : division (assert très utile pour éviter division par zéro)"""
    assert b != 0, "Division par zéro interdite"
    return a / b


# 4. Test : L est une liste non vide
def test_liste_non_vide(L):
    assert isinstance(L, list) and len(L) > 0, "L doit être une liste non vide"


# 5. Test : a ≤ b ≤ c
def test_ordre(a, b, c):
    assert a <= b <= c, "On doit avoir a ≤ b ≤ c"


# 6. Test : n est un carré parfait
def test_carre_parfait(n):
    assert isinstance(n, int) and n >= 0, "n doit être un entier positif ou nul"
    root = int(math.sqrt(n))
    assert root * root == n, f"{n} n'est pas un carré parfait"


# =============================================
# Exercice 2 : Algorithme d'Euclide
# =============================================

def euclide(a, b):
    """Entrée : deux entiers naturels a et b tels que a >= b 
    Sortie : pgcd(a,b)"""
    assert a >= b and isinstance(a, int) and isinstance(b, int), \
           "a et b doivent être des entiers naturels avec a >= b"
    
    while b != 0:
        a, b = b, a % b   # a devient b, b devient le reste
    
    return a


# Question 2 : help(euclide) renvoie la docstring + signature de la fonction


# Question 3 : Fonction de terminaison
# Variante : la valeur de b (entier >= 0 qui décroît strictement à chaque itération)


# =============================================
# Exercice 3 : Primalité - Algorithme naïf
# =============================================

def premier(n):
    """Renvoie True si n est premier, False sinon (version naïve)"""
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


# Test sur les entiers de 1 à 20
print("Nombres premiers de 1 à 20 (naïf) :", end=' ')
for i in range(1, 21):
    if premier(i):
        print(i, end=' ')
print()


# =============================================
# Exercice 4 : Primalité - Algorithme moins naïf
# =============================================

def est_premier(n):
    """Renvoie True si n est premier (optimisé jusqu'à √n)"""
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True


# Test sur les entiers de 1 à 20
print("Nombres premiers de 1 à 20 (optimisé) :", end=' ')
for i in range(1, 21):
    if est_premier(i):
        print(i, end=' ')
print()


# 3. Nombre de premiers inférieurs à 1000
compte = sum(1 for i in range(1000) if est_premier(i))
print(f"Nombre de premiers < 1000 : {compte}")


# 4. Plus petit premier > 1000
n = 1001
while not est_premier(n):
    n += 2
print(f"Plus petit premier > 1000 : {n}")


# =============================================
# Exercice 5 : Crible d'Ératosthène
# =============================================

def Crible(N):
    """Renvoie une liste C où C[i] = True si i est premier"""
    if N < 0:
        return []
    C = [True] * (N + 1)
    C[0] = C[1] = False
    
    for i in range(2, int(math.sqrt(N)) + 1):
        if C[i]:                                 # i est premier
            for multiple in range(i*i, N+1, i):
                C[multiple] = False
    return C


# Vérification pour N=20
C1 = Crible(20)
print("Nombres premiers < 20 (Crible) :", end=' ')
for n in range(20):
    if C1[n]:
        print(n, end=' ')
print()


# Nombre de premiers inférieurs à 1000 avec crible
C1000 = Crible(1000)
print(f"Nombre de premiers < 1000 (Crible) : {sum(C1000)}")


# =============================================
# Exercice 6 : Comparaison des temps d'exécution
# =============================================

def TestTemps(N):
    # Méthode 1 : Algorithme naïf
    t1 = time()
    C_naif = [premier(i) for i in range(N+1)]
    t_naif = time() - t1
    
    # Méthode 2 : Algorithme optimisé
    t2 = time()
    C_opt = [est_premier(i) for i in range(N+1)]
    t_opt = time() - t2
    
    # Méthode 3 : Crible d'Ératosthène
    t3 = time()
    C_crible = Crible(N)
    t_crible = time() - t3
    
    return t_naif, t_opt, t_crible


# Tests de comparaison
for N in [100, 10**4, 10**5]:
    tn, to, tc = TestTemps(N)
    print(f"\nPour N = {N}:")
    print(f"  Naïf      : {tn:.4f} s")
    print(f"  Optimisé  : {to:.4f} s")
    print(f"  Crible    : {tc:.4f} s")