Trong buổi học Toán tiếp theo, Thầy lại cho ôn tập về số học, trong đó có các khái niệm: ước số, số chính phương, số nguyên tố, … và cho bài tập về nhà cho cả lớp tự luyện tập.

Khái niệm:

• Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương (lũy thừa bậc 2) của một số nguyên.

• Số nguyên \(b\ (b
  eq 0)\) gọi là ước số của số nguyên \(a\), nếu \(a\) chia hết cho \(b\).

• Số nguyên tố là số tự nhiên chỉ có 2 ước số, gồm 1 và chính nó.

Yêu cầu: Bài tập về nhà Thầy cho dãy số A có \(n\) phần tử \(a_{1},a_{2},\ldots,a_{n}\ \)và hỏi có bao nhiêu số có đúng 3 ước số dương trong dãy số A.

Dữ liệu vào:

+ Dòng 1: Chứa duy nhất số nguyên dương \(n\ (1 \leq n \leq 10^{4})\).

+ Dòng 2: Gồm n số nguyên dương \(a_{i}\ (0 < a_{i} \leq 10^{9}:\forall 1 \leq i \leq n)\), giữa các số cách nhau bởi một dấu cách.

Kết quả:

+ Ghi duy nhất số nguyên dương là số lượng số có đúng 3 ước số dương. Nếu không có số nào thỏa mãn thì ghi 0.

Ví dụ:

Ràng buộc:

• \(1 \leq n \leq 10^{4};\ 0 < a_{i} \leq 10^{9}\)\(1 \leq n \leq 10^{4};\ 0 < a_{i} \leq 10^{9}:\forall 1 \leq i \leq n\) .