2769 - Trei Prime

Cerinţa

Se dă un număr natural n care este produs de trei numere prime distincte. Ştiind că există m numere naturale prime cu n şi mai mici decât acesta, să se afişeze în ordine crescătoare cele trei numere prime din descompunerea lui n.

Date de intrare

Programul citește de la tastatură numerele n şi m.

Date de ieşire

Programul va afișa pe ecran numerele prime din descompunerea lui n.

Restricții și precizări

• 1 ≤ m ≤ n ≤ 10*18

Exemplu

Intrare

66 20

Ieșire

2 3 11

Explicație

Avem 66=2•3•11 şi există 20 de numere prime cu 66, mai mici decât acesta.

Rezolvare

import math

def validare_date(n, m):
    if not (1 <= m <= n <= 10**18):
        return False
    return True

if __name__ == '__main__':
    # Citim valorile de la tastatură
    n = int(input("Introduceti numarul n: "))
    m = int(input("Introduceti numarul m: "))

    # Validăm datele de intrare
    if not validare_date(n, m):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        # Initializam variabilele
        factori = []
        numar_prim = 0

        # Factorizam numarul n
        while n > 1:
            for i in range(2, int(math.sqrt(n))+1):
                if n % i == 0:
                    factori.append(i)
                    n //= i
                    break
            else:
                factori.append(n)
                n //= n

        # Numaram factorii primi care sunt mai mici decat n si sunt, de asemenea, primi
        for factor in factori:
            if factor < n and all(factor % i != 0 for i in range(2, int(math.sqrt(factor))+1)):
                numar_prim += 1

        # Afisam cei trei factori primi distincti ai lui n in ordine crescatoare
        print(sorted(set(factori))[:3])
        print("\nDatele de intrare corespund restricțiilor impuse.\n")

Explicație rezolvare

Acest program calculează factorii primi ai unui număr natural dat și afișează cele trei numere prime distincte care alcătuiesc acel număr, precum și numărul de numere prime mai mici decât numărul dat și le afișează pe ecran. Programul verifică mai întâi dacă datele de intrare sunt valide și apoi factorizează numărul dat pentru a găsi factorii primi. În cele din urmă, programul afișează cele trei numere prime distincte din lista factorilor primi și confirmă că datele de intrare sunt valide.