Đề bài
Từ 1 đến 100 có bao nhiêu số nguyên tố? Từ 50 đến 60 thì sao? Hãy đếm các số nguyên tố p thỏa mãn low ≤ p ≤ high. Lưu ý rằng 0 và 1 không phải số nguyên tố. Một cái sàng đến high sẽ trả lời câu hỏi này rất nhanh.
Hãy viết count_primes_in_range(low, high).
Đầu vào
low: Cận dưới, được tính vào đoạn.
high: Cận trên, được tính vào đoạn.
Đầu ra
Trả về số lượng số nguyên tố trong đoạn. Nếu low > high thì đoạn rỗng và đáp án là 0.
Ràng buộc
0 ≤ low ≤ 1,000,000
0 ≤ high ≤ 1,000,000
Ví dụ
Đầu vào:
low = 1
high = 100
Kết quả mong đợi:
expected = 25
Đầu vào:
long long low = 1;
long long high = 100;
Kết quả mong đợi:
long long expected = 25;
Đầu vào:
long low = 1;
long high = 100;
Kết quả mong đợi:
long expected = 25;
Giải thích
Từ 1 đến 100 có 25 số nguyên tố (2, 3, 5, … 97), nên đáp án là 25.
Đầu vào:
low = 50
high = 60
Kết quả mong đợi:
expected = 2
Đầu vào:
long long low = 50;
long long high = 60;
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long low = 50;
long high = 60;
Kết quả mong đợi:
long expected = 2;
Giải thích
Giữa 50 và 60 chỉ có 53 và 59 là số nguyên tố, nên đáp án là 2.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Dựng sàng đến high, gạch bỏ các bội của mỗi số nguyên tố bắt đầu từ bình phương của nó.
Gợi ý 2
Sau đó đếm các số vẫn còn được đánh dấu là nguyên tố trong đoạn từ low đến high.
Gợi ý 3
Nếu low lớn hơn high thì không cần tính gì cả.
Độ phức tạp mong đợi
thời gian O(high log log high), bộ nhớ phụ O(high)
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.