Solução Informática Avançado – Semana 52 – Problema 2

Solução por Lúcio Cardoso

Para resolver o problema, usaremos o conceito de prime gaps.

Um prime gap é a diferença entre números primos consecutivos. Isto é, o $$i$$-ésimo prime gap é igual a $$p_{i+1}-p_i$$, onde $$p_i$$ é o $$i$$-ésimo número primo.

Um fato importante é que para números primos menores do que $$2*10^9$$, o maior prime gap entre eles é menor que $$300$$. Com isso, para resolver o problema, podemos simplesmente iterar pelos números maiores ou iguais a $$N$$ em sequência, e assim que encontrarmos um número primo, imprimimos este número e terminamos o programa. Para checar se um número é primo, é suficiente usar o teste de primalidade comum em $$O(sqrt(n))$$.

Com isso, a complexidade final do problema será $$O(300\cdot sqrt(N))$$. Confira o código para melhor entendimento:

https://gist.github.com/luciocf/abda06db5e718c2aedb37790e473cee7