HSGTR2021_NGTO
Hai bạn An và Bình đang cùng nhau học về sàng nguyên tố Eratosthenes.
Thuật toán sàng nguyên tố để tìm các số nguyên tố từ 2 tới \(n\) như sau:
Viết tất cả các số nguyên từ 2 tới \(n\) theo đúng thứ tự.
Tìm số nguyên nhỏ nhất chưa bị gạch. Gọi số đó là \(p\), \(p\) sẽ là số nguyên tố.
Gạch bỏ \(p\) và tất cả các bội của nó.
Nếu tất cả các số chưa bị gạch bỏ, quay lại bước 2.
Yêu cầu: Cho trước \(n\) và \(k\), hãy tìm số thứ \(k\) sẽ bị gạch bỏ.
Input
- Gồm một dòng chứa số hai nguyên \(n\) và \(k (2≤k≤n≤1000).\)
Các số trên cùng một dòng được ghi cách nhau một khoảng trắng.
Output
- Gồm một số duy nhất là số thứ \(k\) sẽ bị gạch bỏ.
Sample Input
10 7
Sample Output
9
Giải thích
Giải thích: Các số lần lượt bị gạch bỏ sẽ là 2, 4, 6, 8, 10, 3, 9, 5, 7. Số thứ 7 bị gạch bỏ là số 9
Comments