Đếm số nguyên tố

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

bin9638

Dạng bài

Điểm: 400 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hôm nay coder bin9638 top 1 thế giới nhận lời thách đấu của coder thứ 7 tỉ thế giới algorit solo giải 1 bài toán do giáo sư nhphucqt đưa ra.

Bài toán là cho 2 số tự nhiên \(l,r\). Hãy đếm số lượng số nguyên tố giữa chúng.

bin9638 loay hoay mãi mà vẫn chưa nghĩ ra cách làm trong khi algorit đã sắp xong, các bạn hãy giúp bin9638 chiến thắng trong cuộc solo này nhé. Nếu giải được thì bin9638 sẽ chia 1 nửa phần thưởng của cuộc solo này cho các bạn đó !

- Yêu cầu: đếm số lượng số nguyên tố trong đoạn \([l,r]\)

Input

Dòng đầu tiên chứa số nguyên dương \(q\) là số đoạn \([l,r]\)
\(q\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(l\) và \(r\)

Output

Gồm \(q\) dòng, dòng thứ \(i\) ghi một số là số các số nguyên tố trong đoạn \([l,r]\) thứ \(i\) đã cho.

Constraints

\(1 \leq l,r \leq 2 \times 10^8\)
\(1 \leq q \leq 10^5\)

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(q \leq 10^3\), \(l\) và \(r \leq 10^7\)
Subtask \(2\) (\(50\%\) số điểm): \(q \leq 10^5\), \(l\) và \(r \leq 2 \times 10^8\)