Hướng giải: GCD

Nguồn: Free Contest

Chúng ta tìm một số ~p~ nguyên tố mà ước chung lớn nhất của các số nguyên còn lại có thể chia hết là lớn nhất. Tập có các số nguyên còn lại chia hết cho số nguyên tố ~p~ chính là tập số còn lại. Chính vì thế số lượng số cần bỏ đi chính là ~N -~ số phần tử trong tập còn lại. Để làm được điều này, ta sẽ sử dụng thuật toán sàng nguyên tố và tìm ước chung lớn nhất bằng thuật toán Euler.

Độ phức tạp: ~O(Max(a_i))~.