FUTURE NUMBER 2

Xem PDF

Điểm: 250 (p) Thời gian: 0.9s Bộ nhớ: 64M 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\)\(2\) ước thực sự là \(2\)\(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 13
Output
5
Note


Bình luận


  • 0
    scratch_huykhanh 8:48 p.m. 7 Tháng 9, 2023

    sao bài này mình thử trong test thì đúng(thử lẫn test ví dụ + testcase của bài) nhưng nộp lên lại bị WA vậy ạ


    • 0
      SadBoyeer 11:49 a.m. 13 Tháng 6, 2022

      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


      • 1
        giaminh2211 9:17 a.m. 21 Tháng 3, 2022 đã chỉnh sửa

        Bài này memory limit căng quá.


        • 2
          stack_queue_4977 3:24 p.m. 14 Tháng 1, 2022

          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)


          • 2
            phanhuykhang 3:05 p.m. 14 Tháng 1, 2022

            Updated time: 0.9s


            • 0
              huyhau6a2 8:23 a.m. 13 Tháng 1, 2022

              3 tiếng cho việc chỉnh num sieve, tứk thế chứ lị

              2 phản hồi

              • 2
                hongquanyl1 10:11 p.m. 12 Tháng 1, 2022

                :>>>>


                • 0
                  rukashii 8:00 p.m. 12 Tháng 1, 2022

                  Bài này hay đấy =))

                  1 phản hồi

                  • -1
                    rukashii 7:28 p.m. 12 Tháng 1, 2022

                    tác giả có thể thêm giải thích test đề được không 🙁

                    1 phản hồi