Câu 4. ĐOẠN NGUYÊN TỐ

Cho một dãy số nguyên dương 𝐴 = (𝑎1, 𝑎2, … , 𝑎n) (𝑎i ≤ \(10^6\); 1 ≤ 𝑖 ≤ 𝑛). Với mỗi phần tử 𝑎i bạn được phép tăng hoặc giảm một lượng tùy ý để được một số nguyên tố. Khi đó chi phí của bạn cần bỏ ra chính là lượng tăng hoặc giảm đó.
Yêu cầu: Hãy chọn ra một đoạn con gồm 𝑘 phần tử liên tiếp nhau của dãy 𝐴 sao cho tổng chi phí biến đổi mọi phần tử trong đoạn con đó thành các số nguyên tố là nhỏ nhất.
Dữ liệu: Vào từ file DOANNT.INP có cấu trúc như sau:
-Dòng 1: Chứa hai số nguyên dương 𝑛, 𝑘 (1 ≤ 𝑘 ≤ 𝑛 ≤ \(10^5\));
-Dòng 2: Chứa 𝑛 số nguyên dương 𝑎1, 𝑎2, . . , 𝑎n (𝑎i ≤ \(10^6\) ∀𝑖 = 1,2, … , 𝑛).
Kết quả: Ghi ra file DOANNT.OUT một số nguyên duy nhất là tổng chi phí biến đổi nhỏ nhất tìm được.
Ví dụ:

Giải thích: chọn đoạn [5,8], biến đổi 8 → 7 với chi phí là 1.
Giới hạn:

• Có 20% số điểm có 𝑎𝑖 đều là số nguyên tố ∀ 𝑖 = 1,2, … , 𝑛;
• Có 40% số điểm có 𝑛, 𝑘 ≤ 5000; 𝑎𝑖 ≤ 5000 ∀ 𝑖 = 1,2, … , 𝑛;
• Có 40% số điểm còn lại không có ràng buộc bổ sung.