Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Đếm số nguyên tố trong một đoạn

Đếm có bao nhiêu số nguyên tố nằm giữa hai cận, tính cả hai cận.

Bạn sẽ học được gì

  • Đánh dấu hợp số bằng sàng
  • Đếm các giá trị được đánh dấu trong một đoạn
  • Xử lý đoạn rỗng và các số 0, 1

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.