The solution also requires some knowledge of the prime numbers up to $M$. We can use the sieve of Eratosthenes to find them, or the linear sieve for finding all primes up to some number. The final complexity is $O(N + M * \log(\log M))$ or $O(N + M)$, depending on how the sieve is implemented.

h3. Request

h3. -Request- Notice

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

-Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.- Multumim lui ==user(user="Matteoalexandru" type="tiny")== pentru 'traducere':tygyn/solutie_romana