C. PRIMECNT - Đếm số nguyên tố

Bạn được cho biết số và dãy . Để tránh việc phải đọc một lượng dữ liệu quá lớn, dãy sẽ được cho bởi ba số nguyên dương , trong đó mỗi phần tử được xác định theo công thức: .

Có câu hỏi dạng yêu cầu cho biết trong đoạn có bao nhiêu số nguyên tố?

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ;
• Dòng thứ hai chứa ba số nguyên dương xác định dãy ;
• dòng tiếp theo, dòng thứ chứa hai số tương ứng với câu hỏi là trong đoạn có bao nhiêu số nguyên tố.

Dữ liệu ra:

• Ghi trên dòng, dòng thứ ghi câu trả lời cho câu hỏi .

Ví dụ:

Dữ liệu vào:

5 4
2 1 9
1 3 
2 4
3 5
4 4

Dữ liệu vào:

3
2
2
0

Giải thích:

• Dãy ;
• Đoạn là có số nguyên tố;
• Đoạn là có số nguyên tố;
• Đoạn là có số nguyên tố;
• Đoạn là có số nguyên tố.

Giới hạn:

• số điểm ứng với các test có ;
• số điểm ứng với các test có ;
• số điểm ứng với các test có .