Đề bài
Một số nguyên tố là số nguyên lớn hơn 1 chỉ chia hết cho 1 và chính nó. Hãy cộng tất cả các số nguyên tố nhỏ hơn nghiêm ngặt so với limit. Bản thân limit không được tính vào, kể cả khi nó là số nguyên tố.
Cài đặt hàm prime_sum(limit).
Đầu vào
limit: Giới hạn trên (không bao gồm).
Đầu ra
Trả về tổng các số nguyên tố thỏa mãn, hoặc 0 nếu không có số nào.
Ràng buộc
0 ≤ limit ≤ 2,000,000. Trả về tổng dưới dạng số nguyên có dấu 64-bit.
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
Các số nguyên tố nhỏ hơn 12 là 2, 3, 5, 7 và 11; tổng của chúng là 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
Không có số nguyên tố nào nhỏ hơn nghiêm ngặt 2.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chi phí lớn nhất là tìm số nguyên tố hiệu quả; kiểm tra chia hết kiểu ngây thơ cho mọi số sẽ quá chậm.
Gợi ý 2
Dùng cách giống sieve để đánh dấu hợp số, rồi cộng các số còn chưa bị đánh dấu và nhỏ hơn giới hạn.
Gợi ý 3
Nhớ rằng chính giới hạn cũng bị loại trừ, kể cả khi nó là số nguyên tố, và các giới hạn nhỏ có thể không đóng góp gì.
Độ phức tạp mong đợi
thời gian O(limit log log limit), bộ nhớ phụ O(limit)
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.