NGUYÊN TỐ CÙNG NHAU SAU KHI THAM GIA TỔ CHỨC LỄ HỘI LÀNG QUÊ, H...

bài 3. - DE THI HSG
Tin học DE THI HSG

Bài 3. Nguyên tố cùng nhau

Sau khi tham gia tổ chức lễ hội làng quê, Hiếu lại quay trở phòng nghiên cứu TAS và đã tìm

thấy cho mình một lĩnh vực nghiên cứu mới, đó là kĩ thuật mật mã và an toàn thông tin.

Hiếu mong muốn sẽ xây dựng được một phương thức mã hoá thông tin mới có độ an toàn gần

như tuyệt đối. Phương thức mã hoá này được phát triển dựa trên ý tưởng về tập hợp các số

nguyên tố cùng nhau.

Bước đầu tiên của nghiên cứu là: “Từ một tập hợp các số nguyên dương 𝑆, Hiếu muốn chọn

ra một tập con 𝑆′ có số phần tử nhiều nhất sao cho hai số bất kì trong tập con 𝑆′ luôn nguyên

tố cùng nhau”.

Bạn hãy lập trình giúp Hiếu giải quyết vấn đề đơn giản này để Hiếu tập trung làm những phần

việc quan trọng hơn.

Dữ liệu: Vào từ file văn bản COPRIME.INP:

- Dòng đầu tiên ghi số một số nguyên 𝑛 là số lượng các số thuộc tập hợp 𝑆;

- Dòng thứ 𝑖 trong n dòng tiếp theo ghi một số nguyên dương là số thứ 𝑖 của 𝑆.

Kết quả: Ghi ra file văn bản COPRIME.OUT một số nguyên là kích thước lớn nhất của tập

con 𝑆’ của 𝑆 mà hai số bất kì thuộc 𝑆′ nguyên tố cùng nhau.

Ví dụ:

COPRIME.INP COPRIME.OUT

5

2

30

15

6

Ràng buộc:

 Có

1

7

số test ứng với

1

7

số điểm thỏa mãn: các số thuộc tập không vượt quá 20.

 Có

3

7

số test khác ứng với

3

7

số điểm thỏa mãn: các số thuộc tập không vượt quá 100.

7

số điểm thỏa mãn: các số thuộc tập không vượt quá 5000.

7

số test còn lại ứng với

3