P134SUMF spoj PTIT – SUM4 F – Sàng nguyên tố

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P134SUMF/

1. Đề bài P134SUMF spoj PTIT

Tí và Tèo đ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:

1. Viết tất cả các số nguyên từ 2 tới N theo đúng thứ tự.

2. 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ố.

3. Gạch bỏ P và tất cả các bội của nó.

4. Nếu tất cả các số chưa bị gạch bỏ, quay lại bước 2.

Tí đố Tèo rằng, cho trước N và K, hãy tìm số thứ K sẽ bị gạch bỏ.

Input

Chứa 2 số nguyên N và K (2 ≤ K < N ≤ 1000).

Output

Hãy in ra số thứ K sẽ bị gạch bỏ.

Example

Test 1:

Input:

7 3

Output:

6

Test 2:

Input:

15 12

Output:

7

Test 3:

Input:

10 7

Output:

9

Giải thích test 3: Các số lần lượt bị gạch bỏ sẽ là 2, 4, 6, 8, 10, 3, 9, 5, 7.

Do đó số thứ 7 sẽ là 9.

2. Code tham khảo P134SUMF spoj PTIT

Áp dụng thuật toán  sàng nguyên tố Eratosthenes bình thường, 😀 còn lại thì đếm là được.

a. Code pascal

b. Code c++