import math

# construction de la liste de Fibonacci par une méthode itérative
def liste_fibonacci(n):
    liste = [0,1]
    for i in range(2,n+1):
        liste.append(liste[i-1]+liste[i-2])

    return liste

# utilisation d'une fonction optimisée pour déterminer si un nombre
# est premier
def est_premier(n: int) -> bool:
   
    # 1) traiter les cas de base : les nombres inférieurs ou égaux à 1
    if n <= 1:
        return False
   
    # 2) 2 et 3 sont des nombres premiers
    if n <= 3:
        return True
   
    # 3) éliminer rapidement tous les multiples de 2 et de 3
    if n % 2 == 0 or n % 3 == 0:
        return False
   
    # 4) vérifier les facteurs restants jusqu'à la racine carrée de n.
    # Tous les nombres premiers supérieurs à 3 sont de la forme 6k ± 1.
    i = 5
    while i * i <= n:
        # vérifie i (6k - 1) et i + 2 (6k + 1)
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6  # passer au prochain "6k"
       
    return True


def main():
    liste_fib = liste_fibonacci(83)

    print(liste_fib)
   
    for i in range(len(liste_fib)):
        # attention ici il faut vérifier que liste_fib[i] est premier et non pas i !!
        if est_premier(liste_fib[i]):
            print(f"fib({i}) = {liste_fib[i]:,} est premier")

if __name__ == "__main__":
    main()