Paul Matei: Pagină nouă: == 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...

2023-04-29T11:33:46Z

Pagină nouă: == 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...

New page

== 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

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

</syntaxhighlight>

2608 - Bi Prime - Revision history