Bài 33.4. Vấn Đề Chuỗi Khóa Lớn - [Độ khó: Khó]

Mô tả: Trong một hệ thống an ninh mạng mật mã, các "chuỗi khóa an toàn" được định nghĩa là các đoạn số nguyên liên tiếp [L, R] mà tại đó, bạn cần tìm số lượng số nguyên tố. Tuy nhiên, việc kiểm tra từng số một hoặc sử dụng sàng Eratosthenes thông thường là không khả thi vì L và R có thể rất lớn (lên đến \(10^{12}\)), trong khi độ dài đoạn R - L tương đối nhỏ. Nhiệm vụ của bạn là phát triển một thuật toán hiệu quả để đếm số lượng số nguyên tố trong một đoạn [L, R] cho trước.

INPUT FORMAT

Một dòng duy nhất chứa hai số nguyên L và R (\(1 \le L \le R \le 10^{12}\), \(R - L \le 10^6\)).

OUTPUT FORMAT

In ra một số nguyên duy nhất là số lượng số nguyên tố trong đoạn [L, R].

Ví dụ:

Input:

10 20

Output:

4

Giải thích:

• Các số nguyên tố trong đoạn [10, 20] là: 11, 13, 17, 19.
• Có tổng cộng 4 số nguyên tố.
• Trường hợp biên:
  • Nếu L=1, thì số 1 không phải là số nguyên tố và không được tính.
  • Nếu L và R đều là các số nhỏ (ví dụ: [2, 3]), kết quả là 2.
  • Nếu đoạn không có số nguyên tố nào (ví dụ: [8, 9]), kết quả là 0.