Subtask 1

Ta sẽ for lồng và làm theo yêu cầu bài toán, đề bảo gì làm nấy.

Subtask 2

Ta có thể làm như sau:

• Tạo một dãy \(1,2,...,M\) (ta sẽ đặt tên dãy là \(S\)).

• ta sẽ for \(i\) từ \(1\) đến \(N\) và thực hiện như sau:

  • Phân tích \(a_i\) thành thừa số nguyên tố, gọi \(P\) là tập hợp thừa số nguyên tố đó (bạn cần xóa hết các thừa số giống nhau nếu không sẽ bị quá thời gian).
  • Với mọi thừa số nguyên tố \(k\) trong \(P\), xóa vào \(S\) tất cả các bội của \(k\) (sử dụng sàng).

• các số còn tồn tại trong \(S\) là các số thỏa mãn. Bạn chỉ cần in ra.

Mỗi lần phân tích ra thừa số nguyên tố sẽ có độ phức tạp \(O(\sqrt{a_i})\) nên độ phức tạp thuật toán tổng trong trường hợp xấu nhất sẽ là sẽ là \(O(N \times \sqrt{max(a_i)})\).

Subtask 3

Ta có thể giảm \(O(N \times \sqrt{max(a_i)})\) xuống \(O(N \times \log(max(a_i)))\) bằng cách sàng nguyên tố xong phân tích thành thừa số nguyên tố trong \(O(log(a_i))\), còn lại làm tương tự Subtask 2. Bạn có thể tham khảo phân tích thành thừa số nguyên tố trong \(O(log(a_i))\) tại đây.