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\)\(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
    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ị


    • 1
      nguyenminhhai021009    8:41 a.m. 13 Tháng 1, 2022

      có vẻ bạn thích số 3 nhỉ :)))


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

        ngoài số 3 còn nhiều số mình thích nữa như 500, 1001, 7749, ... hehe


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

        code thứ 2 đã ac rồi hehe


      • 2
        PhanHuyKhang    8:32 a.m. 13 Tháng 1, 2022

        hôm qua nói với admin time limit là 0.9s mà chưa thấy admin onl =))

        8 bình luận nữa