Problema
Um número primo é um inteiro maior que 1 divisível apenas por 1 e por ele mesmo. Some todos os primos estritamente menores que limit. O próprio limite é excluído mesmo que seja primo.
Implemente prime_sum(limit).
Entrada
limit: O limite superior exclusivo.
Saída
Retorne a soma dos primos elegíveis, ou 0 caso não exista nenhum.
Restrições
0 ≤ limit ≤ 2.000.000. Retorne a soma usando um inteiro assinado de 64 bits.
Exemplos
Entrada:
limit = 12
Saída esperada:
expected = 28Entrada:
long long limit = 12;
Saída esperada:
long long expected = 28;Entrada:
long limit = 12;
Saída esperada:
long expected = 28;Explicação
Os primos abaixo de 12 são 2, 3, 5, 7 e 11; sua soma é 28.
Entrada:
limit = 2
Saída esperada:
expected = 0Entrada:
long long limit = 2;
Saída esperada:
long long expected = 0;Entrada:
long limit = 2;
Saída esperada:
long expected = 0;Explicação
Não há primos estritamente abaixo de 2.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
O maior custo é encontrar primos com eficiência; testes ingênuos de divisibilidade para todo número serão lentos demais.
Dica 2
Use uma abordagem tipo crivo para marcar compostos e depois some os números que ficaram desmarcados e abaixo do limite.
Dica 3
Lembre que o próprio limite é excluído, mesmo quando é primo, e limites pequenos podem não contribuir com nada.
Complexidade esperada
tempo O(limit log log limit), espaço extra O(limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.