Условие
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.
Ограничения
0 ≤ limit ≤ 2,000,000. Return the sum using a signed 64-bit integer.
Примеры
Ввод:
limit = 12
Ожидаемый вывод:
expected = 28Ввод:
long long limit = 12;
Ожидаемый вывод:
long long expected = 28;Ввод:
long limit = 12;
Ожидаемый вывод:
long expected = 28;Пояснение
The primes below 12 are 2, 3, 5, 7, and 11; their sum is 28.
Ввод:
limit = 2
Ожидаемый вывод:
expected = 0Ввод:
long long limit = 2;
Ожидаемый вывод:
long long expected = 0;Ввод:
long limit = 2;
Ожидаемый вывод:
long expected = 0;Пояснение
There are no primes strictly below 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
The main cost is finding primes efficiently; naive divisibility checks for every number will be too slow.
Подсказка 2
Use a sieve-like approach to mark composites, then add the numbers that remain unmarked and below the limit.
Подсказка 3
Remember that the limit itself is excluded, even when it is prime, and small limits may contribute nothing.
Ожидаемая сложность
O(limit log log limit) time, O(limit) extra space
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.