Nguồn đề bài: http://vn.spoj.com/problems/HSPC14J/
Nội dung bài viết
1. Đề bài HSPC 2014
Sàng của Eratosthenes là thuật toán nổi tiếng để tìm tất cả các số nguyên tố nhỏ hơn N. Thuật
toán như sau:
- Ghi ra tất cả các số nguyên giữa 2 và N.
- Tìm số nhỏ nhất chưa bị gạch và gọi nó là P (P là số nguyên tố).
- Gạch bỏ P và tất cả các bội số của nó mà chưa bị gạch.
- Nếu còn số chưa bị gạch bỏ, chuyển sang bước 2.
Viết một chương trình, cho N và K, tìm số nguyên thứ K bị gạch.
Input
Gồm nhiều bộ test, mỗi bộ test nằm trên một dòng gồm các số nguyên N và K (2 ≤ K < N ≤ 1000).
Output
Với mỗi test, in ra trên một dòng số thứ K bị gạch bỏ.
Example
Input:
7 3
15 12
10 7
Output:
6
7
9
2. Code tham khảo HSPC14J spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | const fi=''; nmax=1000; type data=longint; var f:text; x,M:data; A:array[1..nmax] of boolean; procedure xuli; var i,j,k:data; begin for i:=1 to x do a[i]:=false; i:=2; k:=0; while i<=x do begin if not a[i] then begin for j:=1 to x div i do if not a[i*j] then begin inc(k); if k=m then begin writeln(i*j); exit; end; a[i*j]:=true; end; end; inc(i); end; end; begin assign(f,fi); reset(f); while not eof(f) do begin readln(f,x,m); xuli; end; end. |
Bài viết liên quan
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- COIN34 spoj – 34 Đồng Xu
- PTIT013K spoj PTIT – SỐ NGUYÊN HỆ CƠ SỐ ACM
- P147PROB spoj PTIT – Pha nước cam
- P141PROB spoj PTIT – Tuần lễ công dân
- BCTHIDAU spoj PTIT – Thi đấu
- MYSTERY spoj – Số huyền bí
- VECTOR spoj – Tổng Vector