Đề bài
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.
Ràng buộc
0 ≤ limit ≤ 2,000,000. Return the sum using a signed 64-bit integer.
Ví dụ
Đầu vào:
limit = 12
Kết quả mong đợi:
expected = 28Đầu vào:
long long limit = 12;
Kết quả mong đợi:
long long expected = 28;Đầu vào:
long limit = 12;
Kết quả mong đợi:
long expected = 28;Giải thích
The primes below 12 are 2, 3, 5, 7, and 11; their sum is 28.
Đầu vào:
limit = 2
Kết quả mong đợi:
expected = 0Đầu vào:
long long limit = 2;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long limit = 2;
Kết quả mong đợi:
long expected = 0;Giải thích
There are no primes strictly below 2.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
The main cost is finding primes efficiently; naive divisibility checks for every number will be too slow.
Gợi ý 2
Use a sieve-like approach to mark composites, then add the numbers that remain unmarked and below the limit.
Gợi ý 3
Remember that the limit itself is excluded, even when it is prime, and small limits may contribute nothing.
Độ phức tạp mong đợi
O(limit log log limit) time, O(limit) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.