Editing 4196 - MPF

== Enunt ==
Fie '''X''' un număr natural nenul și '''p''' cel mai mare factor prim din descompunerea în factori primi a lui '''X'''. Pentru '''X = 1''', considerăm '''p = 1'''. Asupra lui '''X''' se pot efectua următoarele două operații:

Operația 1: '''X''' se împarte la '''p''' și devine '''X / p''';
Operația 2: '''X''' devine '''X * k''', unde '''k''' este un număr prim și mai mare sau egal decât '''p'''.
== Cerinţa ==
Se dau '''Q''' perechi de numere naturale nenule '''(X, Y)'''. Să se determine, pentru fiecare pereche, numărul minim de operații necesare pentru a-l transforma pe '''X''' în '''Y'''.
== Date de intrare ==
Datele de intrare conțin '''Q + 1''' linii. Pe prima linie se găsește '''Q''' reprezentând numărul de perechi '''(X, Y)'''.
Pe următoarele '''Q''' linii, câte o pereche de numere naturale nenule '''X''' și '''Y''', despărțite printr-un singur spațiu.
== Date de ieșire ==
Ieșirea va conține '''Q''' linii. Pe fiecare linie '''i''' se va scrie câte un număr natural reprezentând, numărul de operații determinat pentru a i-a pereche.
== Restricţii şi precizări ==
* '''1 ≤ Q ≤ 1.000.000'''
* '''1 ≤ X, Y ≤ 4.000.000'''
Datorită dimensiunii mari a datelor de intrare și de ieșire, doar unele teste au fost adăugate.
== Exemplul 1 ==
; Intrare

4
4 10
2 9
6 2
12 12
; Ieșire

2
3
1
0
== Explicație == 
Pentru (4, 10): 4 devine 2 utilizând o Operație 1, apoi devine 10 utilizând o Operație 2.
Pentru (2, 9): 2 devine 1 utilizând o Operație 1, apoi devine 3 folosind o Operație 2 și devine 9 folosind o Operație 2.
Pentru (6, 2): 6 devine 2 folosind o Operație de tip 1.
Pentru (12, 12): Numerele sunt egale, nu este necesară nicio operație.
<br>



== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_prime_factor(x):
    factor = 2
    while factor * factor <= x:
        if x % factor == 0:
            x //= factor
        else:
            factor += 1
    return x

with open("input.in", "r") as fin:
    q = int(fin.readline())
    pairs = [tuple(map(int, line.split())) for line in fin]

with open("output.out", "w") as fout:
    for pair in pairs:
        x, y = pair
        if x == y:
            fout.write("0\n")
        elif max_prime_factor(x) == max_prime_factor(y):
            fout.write("1\n")
        else:
            fout.write("2\n")

</syntaxhighlight>