FUTURE NUMBER 2
Xem PDF
Điểm:
250 (p)
Thời gian:
0.9s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Định nghĩa: Số "tương lai" là số có các ước (không kể \(1\) và chính nó) là các số nguyên tố.
Ví dụ: \(10\) có \(2\) ước thực sự là \(2\) và \(5\) là các số nguyên tố nên \(10\) là số "tương lai".
Yêu cầu: Cho dãy số nguyên \(a_1,a_2,...a_n\) (\(1 \le n \le 10^6 ,1 \le a_i \le 2 \times 10^7\)). Hãy cho biết trong dãy trên có bao nhiêu số tương lai.
Input
- Dòng thứ nhất gồm số nguyên \(n\).
- Dòng thứ hai gồm các số \(a_1,a_2,...,a_n\).
Example
Test 1
Input
9
9 7 10 6 17 4 19 21 13Output
5Note
Bình luận
Có cách nào mà không dùng sàng O(cbrt(1e7)) mà vẫn AC không nhỉ?
Mình sàng lưu ước nguyên tố nhỏ nhất rồi phân tích thành thừa số nguyên tổ mà tổng số mũ == 2 thì mình tăng biến đếm
8 bình luận nữa