#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 19 06:30:46 2021

@author: phjo
"""

# ma préférence :
def estPremier(n):
    d = 2
    while d*d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

from math import sqrt

# possible avec une boucle for, mais il y a le problème
# de la racine carrée à convertir en un entier.
# round évite le risque que int(sqrt(n)) pourrait,
# si n est un carré parfait, ne pas être la racine carrée
# de n...
def estPremier2(n):
    for d in range(2, round(sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

def liste_premiers(n):
    L = []
    for i in range(2, n+1):
        if estPremier(i):
            L.append(i)
    return L

def valuation_p_adique(n, p):
    v = 0
    while n % p == 0:
        v += 1
        n //= p
    return v

def val(n, p):
    if n % p != 0:
        return 0
    return val(n // p, p) + 1



# vite fait, peu efficace, mais solution à privilégier dans ce genre d'exercice
def decomp2(n):
    L = []
    for p in liste_premiers(n):
        if n % p == 0:
            L.append([p, valuation_p_adique(n, p)])
    return L
        

# version plus efficace, bien qu'élémentaire, mais il n'est pas
# certain que cette version plus longue à écrire rapporte plus
# de points...
def decomposition_facteurs_premiers(n):
    d = 2
    dec = []
    while n > 1:
        if n % d == 0:
            val = 1
            n //= d
            while n % d == 0:
                val += 1
                n //= d
            dec.append([d, val])
        if d == 2:
            d = 3
        else:
            d += 2
    return dec