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:
| // Noic – Avançado – Semana 52 – Problema 2 | |
| // O(300 * sqrt(N)) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| // teste de primalidade | |
| bool isprime(int x) | |
| { | |
| if (x == 1) return false; | |
| for (int i = 2; i*i <= x; i++) | |
| if (x%i == 0) | |
| return false; | |
| return true; | |
| } | |
| int main(void) | |
| { | |
| int n; | |
| scanf("%d", &n); | |
| // loop principal | |
| while (!isprime(n)) n++; | |
| printf("%d\n", n); | |
| } |

Comente