Số thứ k được xoá

cho em hỏi ý tưởng để làm bài này là gì ạ?
Viết các số tự nhiên từ 2, 3, 4, …, n trên mặt bàn và tiến hành xóa các số đó như sau:

Chọn số nhỏ nhất chưa xóa (gọi là số x ), xóa số x và tất cả các số chưa xóa là bội của x (thứ tự các số được xóa từ số nhỏ đến số lớn) và cứ tiếp tục quay lại như vậy.

Yêu cầu: Tìm xem, số thứ k được xóa là số nào.

Dữ liệu:

  • gồm hai số nguyên dương nk được ghi trên một dòng ( k<n<10^7).

Kết quả:

- là số thứ k được xóa.

Để ý rằng bài tương tự sàng Eratosthenes.

2 Likes

em cảm ơn :blush::blush::blush::blush::blush::blush:

em code như thế này

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,u[100005],d=1;
bool dd[100005];
int main()
{
memset(u,0,sizeof(u));
memset(dd,true,sizeof(dd));
cin>>n>>k;
for(ll i =2;i<=n;i++)
{
if(dd[i]==true){
u[d]=i;d++;
for(ll j=i*i;j<=n;j+=i)
{
dd[j]=false;
u[d]=j;
d++;
}
}
}
cout<<u[k];
}

không biết có cách code nào nhanh hơn ko ạ

em làm như trên bị time limited ở test
9999999 9999998

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?