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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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