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:


// 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);
}