Pentru problema existau diverse rezolvari brute-force, care in functie de calitatea implementarii af fi obtinut pana la $50$ de puncte.
Algoritmul folosit in rezolvarea pentru $100$ de puncte este Miller-Rabin. Este un algoritm probabilistic care verifica primalitatea unui numar in complexitate $O(c*log Nr)$, unde c este numarul de baze folosite pentru verificare.

Dorim sa verificam daca numarul Nr este prim. Primul pas care trebuie efectuat este acela de a-l scrie pe $Nr-1$ ca numar de forma <tex>2^s^ * d</tex>, unde s trebuie sa fie maxim. Pasul urmator este sa verificam 2 relatii:

Dorim sa verificam daca numarul $Nr$ este prim. Primul pas care trebuie efectuat este acela de a-l scrie pe $Nr-1$ ca numar de forma <tex>2^s^ * d</tex>, unde s trebuie sa fie maxim. Pasul urmator este sa verificam 2 relatii:

1. <tex> a^{d}\ mod\ n\ \neq\ 1 </tex>
2. <tex> a^{2^r*d}\ mod\ n\ \neq\ -1</tex>, pentru $0 &le; r &le; s-1$