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
(đã xóa 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
Bài này memory limit căng quá.
Update: Đã update time (1.0 \(\rightarrow\) 0.9s)
Còn về phần rejudge thì mình sẽ thực hiện vào sáng sớm mai (15/1/22) (để tránh quá tải máy chấm)
Updated time: 0.9s
3 tiếng cho việc chỉnh num sieve, tứk thế chứ lị
:>>>>
Bài này hay đấy =))
tác giả có thể thêm giải thích test đề được không 🙁