0062 - Factorizare

Cerinţa

Se citeşte un număr natural n. Să se afişeze descompunerea în factori primi a lui n.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul afișează pe ecran perechile b p, reprezentând factorii primi şi puterile corespunzătoare. Perechile se afişează câte una pe o linie a ecranului, în ordinea crescătoare a bazelor. Cele două valori din pereche sunt separate printr-un spaţiu.

Restricții și precizări

• 1 < n < 2.100.000.000

Exemplu

Intrare

135

Ieșire

3 3

5 1

Explicație

• 135 = 33 * 51.

Rezolvare

import math


def validare_natural(n):
    try:
        n = int(n)
        if n > 1 and n < 2100000000:
            return n
        else:
            print("Numarul trebuie sa fie un numar natural mai mare decat 1 si mai mic decat 2100000000.")
            return None
    except ValueError:
        print("Nu ati introdus un numar natural valid.")
        return None


n = input("Introduceti numarul n: ")
n = validare_natural(n)


if n:
    i = 2
    while i <= n:
        p = 0
        while n % i == 0:
            p += 1
            n //= i
        if p > 0:
            print(i, p)
        i += 1