HSPC14J spoj - Sàng - Kiến Thức 24h

Nguồn đề bài: http://vn.spoj.com/problems/HSPC14J/

Nội dung bài viết

1. Đề bài HSPC 2014
2. Code tham khảo HSPC14J spoj

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.

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;

inc(i);

end;

begin

assign(f,fi); reset(f);

while not eof(f) do

begin

readln(f,x,m);

xuli;

end;

end.

HSPC14J spoj – Sàng

1. Đề bài HSPC 2014

Input

Output

Example

2. Code tham khảo HSPC14J spoj

Bài viết liên quan

Trả lời Hủy