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

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

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. Code c++

#include<stdio.h>
#include <cmath>
#include <iostream>

using namespace std;

int main()
{
     int i,j,*a,k,count=0,n;
     cin >> n >> k;
     a=new int[n+1];
     for(i=2;i<=n;i++)
     a[i]=1;
     for(i=2;i<=n/2;i++)
     for(j=1;j<=n/i;j++)
     {
         if(a[i*j]==1)   //nếu là số chưa xử lý thì xóa đến hết n số
         {
            a[i*j]=0;
            count++;
            if(count==k)
                cout << i*j;
         }
    }
}