2608 - Bi Prime

Cerinţa

Se dă n un număr natural care este produsul a două numere prime distincte, şi m reprezentând numărul numerelor mai mici sau egale cu n, prime cu n. Aflaţi cele două 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, în ordine crescătoare, separate prin spaţiu.

Restricții și precizări

• 1 ≤ m ≤ n ≤ 10*25

Exemplu

Intrare

8777 8580

Ieșire

67 131

Explicație

Avem 8777=67•131

Rezolvare

import math

# functie pentru a calcula cel mai mare divizor comun
def cmmdc(a, b):
    if b == 0:
        return a
    return cmmdc(b, a % b)

# functie pentru a determina un factor al lui n folosind metoda lui Pollard-Rho
def pollard_rho(n):
    x = 2
    y = 2
    d = 1
    while d == 1:
        x = (x * x + 1) % n
        y = (y * y + 1) % n
        y = (y * y + 1) % n
        d = cmmdc(abs(x - y), n)
    return d

# functie pentru a valida datele de intrare
def validare_date(n, m):
    if n < 1 or m < 1 or n > 10**25 or m > n:
        return False
    return True

if __name__ == '__main__':
    # citim numerele n si m de la tastatura
    n, m = map(int, input().split())

    # validam datele de intrare
    if validare_date(n, m):
        # factorizam n folosind metoda lui Pollard-Rho
        factor1 = pollard_rho(n)
        factor2 = n // factor1

        # calculam numarul de numere prime mai mici sau egale cu n, prime cu n
        phi = (factor1 - 1) * (factor2 - 1)

        # afisam cei doi factori primi ai lui n in ordine crescatoare
        print(min(factor1, factor2), max(factor1, factor2))
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")