Câu 4. (1,0 điểm) ƯỚC Cho dãy n số nguyên dương a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10¹²). Yêu cầu: Cho biết trong dãy có bao nhiêu số có đúng 3 ước số. Dữ liệu vào: Tệp văn bản UOC.INP gồm hai dòng: Dòng đầu ti...

Để giải bài toán này, ta cần xác định số lượng các số trong dãy có đúng 3 ước số. **Phân tích bài toán:** - Một số có đúng 3 ước số khi và chỉ khi số đó là bình phương của một số nguyên tố. - Ví dụ: 4 = 2² có 3 ước số: 1, 2, 4. - Vì số có dạng p² (p là số nguyên tố) thì ước số của nó là: 1, p, p² → đúng 3 ước số. **Ý tưởng giải:** 1. Với mỗi số aᵢ trong dãy: - Kiểm tra xem aᵢ có phải là số chính phương không (tính căn bậc hai nguyên của aᵢ). - Nếu đúng là số chính phương, giả sử aᵢ = x², thì kiểm tra xem x có phải là số nguyên tố không. 2. Đếm số lượng các số thỏa mãn điều kiện trên. **Vấn đề cần giải quyết:** - Với aᵢ có thể lên đến 10¹², căn bậc hai của aᵢ có thể lên đến 10⁶. - Kiểm tra nguyên tố cho các số đến 10⁶ có thể thực hiện bằng cách: - Dùng sàng Eratosthenes để tạo bảng đánh dấu số nguyên tố đến 10⁶. - Hoặc kiểm tra nguyên tố trực tiếp với thuật toán kiểm tra nhanh. **Cách làm cụ thể:** - Đọc n và dãy a. - Tạo bảng sàng Eratosthenes đánh dấu số nguyên tố đến 10⁶. - Với mỗi aᵢ: - Tính x = căn bậc hai của aᵢ (làm tròn xuống). - Nếu x * x == aᵢ và x là số nguyên tố (theo bảng sàng), tăng biến đếm. - In ra kết quả. --- Bạn cần mình hỗ trợ viết code mẫu hoặc hướng dẫn chi tiết hơn không?