Đếm số nguyên tố trong [L,R] (Count Primes in an Interval)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai số nguyên $L,R$ với $0\le L\le R\le20000$. Đếm các số nguyên tố trong đoạn đóng $[L,R]$. Số nguyên tố là số nguyên lớn hơn 1 có đúng hai ước dương là 1 và chính nó. Không tính 0 hoặc 1 là số nguyên tố. Bài này giải bằng vòng lặp kiểm ước trực tiếp; không cần sàng hay mảng.

Input

Một dòng chứa $L$ và $R$, phân tách bằng dấu cách.

Output

In một số nguyên là số lượng số nguyên tố trong đoạn.

Subtask

• Subtask 1 (20%): $0\le L\le R\le 100$.

• Subtask 2 (30%): $0\le L\le R\le 2000$.

• Subtask 3 (50%): $0\le L\le R\le 20000$.

Ví dụ

Ví dụ 1

Input:

0 10

Output:

4

Giải thích:

Trong [0,10] chỉ đếm số >=2 không có ước từ 2 đến căn bậc hai.

Ví dụ 2

Input:

1 1

Output:

0

Giải thích:

Trong [1,1] chỉ đếm số >=2 không có ước từ 2 đến căn bậc hai.