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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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++

One thought on “P134SUMF spoj PTIT – SUM4 F – Sàng nguyên tố

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *