Lại là sàng Eratosthenes

Points: 1

Time limit: 1.0s

Memory limit: 98M

Author:

Problem types

Cho hai số nguyên dương $L$ ≤ $R$ . Hãy đếm xem trong đoạn $[L, R]$ có bao nhiêu số nguyên tố.

Input:

Dòng đầu ghi số nguyên dương $T$ là số bộ test. ( $T$ <= $10^{5}$ )
T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $L, R$ cách nhau bởi một dấu cách. $(1 < L \leq R \leq 10^{8})$

Output:

Với mỗi cặp số $L$ và $R$ , ghi ra trên một dòng số số nguyên tố trong đoạn $[L, R]$ . (Đoạn $[L, R]$ ít hơn $10^{8}$ phần tử)

Example:

Input1:

Copy

2
2 3
10 15

Output1:

Copy

2
2

Input2:

Copy

Output2:

Copy

1
2
6

Comments