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 $2^s^*d$, 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 $2^s^*d$, unde s trebuie sa fie maxim. Pasul urmator este sa verificam 2 relatii:

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

Daca amandoua relatiile sunt simultan indeplinite pentru un numar $a$, atunci stim ca numarul $Nr$ este compus. Daca cel putin una dintre conditii nu este indeplinita se continua verificarile pentru un alt numar &a&. Numerele $a$ cu care se vor face verificarile pot fi, de exemplu, primele 6 numere prime sau o multime de numere prime alese aleator (mai mult de $3$).
 

h2. 'Kcity':problema/kcity