# -*- coding:utf-8 -*-

__projet__ = "CoursS5"
__nom_fichier__ = "9_decomposition"
__author__ = "A-J. Tinet"
__date__ = "décembre 2022"

"""
========================================================================================================================

                                         Ex. 9 - DECOMPOSTION D'UN NOMBRE EN PRODUIT DE FACTEURS

========================================================================================================================
"""

# Définition de fonctions

def premier(n):
    """
    :param n: Nombre entier
    :return: Liste de 0 et de 1, les 1 indiquent un nombre premier
    """
    lpremier = [0,0]+[1]*(n-1)

    for k in range(2, int(n**0.5)+1, 1):

        # Si un nombre k n'est pas premier alors tout ses multiples ont déjà été traités (car multiples des diviseurs de k)
        if lpremier[k] == 1:
            # Les multiples de k plus petits de k**2 ont déjà été traités (car multiples d'un nombre plus petit que k)
            p = k*k

            # Les multiples de k ne sont pas des nombres premiers
            while p <= n:
                lpremier[p] = 0
                p += k

    return lpremier


def decomposition(n):
    """
    :param n: Nombre entier
    :return: Décomposition de n en facteurs premiers, liste de doublets nombre premier, puissance
    """

    # Liste des nombres premiers
    lpremiers = premier(n)

    # Initialisation
    lfacteurs = []

    # Décomposition
    for p in range(len(lpremiers)):
        # On regarde si p est premier et divise n
        if lpremiers[p] == 1 and n%p == 0:

            # On recherche la puissance associée:
            puissance = 0
            while n%p == 0:
                puissance += 1
                n = n//p

            lfacteurs.append((p,puissance))

    return lfacteurs





# Programme principal
if __name__ == '__main__':

    print(premier(7)) #[0,0,1,1,0,1,0,1]
    print(premier(16)) #[0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0]

    print(decomposition(7020)) # [(2,2),(3,3),(5,1),(13,1)]
    print(decomposition(49)) # [(7,2)]
    print(decomposition(71)) # [(71,1)]