Nguồn đề bài: http://vn.spoj.com/problems/HSPC14J/
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
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.
