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

<syntaxhighlight lang="python" line> import math

1. functie pentru a calcula cel mai mare divizor comun

def cmmdc(a, b):

   if b == 0:
       return a
   return cmmdc(b, a % b)

1. 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

1. 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.")

</syntaxhighlight>