02/10/2018, 14:00
HSPC14J spoj – Sàng
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ố ...
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.
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. |
