Solution DMT

Begin

Đánh giá : đây là 1 bài về số nguyên tố khá cơ bản.

• Nhận xét quan trọng: số chia hết cho 3 và có đúng 9 ước nguyên tố thì sẽ có dạng 9 * a ^ 2 (a là số nguyên tố và a khác 3)

• Subtask 1, 2, 3: For trâu để tìm a

• Full :

     Nhận xét : vì Rmax là 1e12 -> a max là 1e6 
     Từ đây ta có thể sàng các số nguyên tố nhỏ hơn 1e6 (không tính 3)  sau đó với mỗi l, r ta tìm kiếm nhị phân 2 đầu mút trái phải của a là [u, v]
     Đáp án sẽ là v - u + 1
  

End.