Todos os desafios
Médio 1 resolvido 100.0% de aceitação

Sum of Primes Below a Limit

Add all primes strictly below a limit.

O que você vai aprender

  • Find all primes below a limit with a sieve
  • Mark multiples instead of testing each number
  • Sum values efficiently

Problema

Ver tradução

A prime is an integer greater than 1 divisible only by 1 and itself. Add every prime strictly smaller than limit. The limit itself is excluded even when it is prime.

Implement prime_sum(limit).

Input

limit: The exclusive upper bound.

Output

Return the sum of the eligible primes, or 0 when none exist.

Restrições

0 ≤ limit ≤ 2,000,000. Return the sum using a signed 64-bit integer.

Exemplos

Exemplo 1
Entrada:
limit = 12

Saída esperada:
expected = 28
Entrada:
long long limit = 12;

Saída esperada:
long long expected = 28;
Entrada:
long limit = 12;

Saída esperada:
long expected = 28;

Explicação

The primes below 12 are 2, 3, 5, 7, and 11; their sum is 28.

Exemplo 2
Entrada:
limit = 2

Saída esperada:
expected = 0
Entrada:
long long limit = 2;

Saída esperada:
long long expected = 0;
Entrada:
long limit = 2;

Saída esperada:
long expected = 0;

Explicação

There are no primes strictly below 2.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

The main cost is finding primes efficiently; naive divisibility checks for every number will be too slow.

Dica 2

Use a sieve-like approach to mark composites, then add the numbers that remain unmarked and below the limit.

Dica 3

Remember that the limit itself is excluded, even when it is prime, and small limits may contribute nothing.

Complexidade esperada

O(limit log log limit) time, O(limit) extra space

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 ННикита Python 1,057 ms - 4/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 1 solução completa abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.