Solution

วิธีทำข้อนี้คือให้สร้าง Array ที่มีขนาด $N+1$ ช่อง โดยแต่ละช่องจะมีค่า $0$ กับ $1$ เท่านั้น (ถ้า Array ช่องที่ $x$ มีค่าเท่ากับ $0$ แปลว่าเลข $x$ ยังไม่ถูกขีดฆ่า แต่ถ้าเป็น $1$ แปลว่าถูกขีดฆ่าแล้ว)

ให้ $c$ คือเลขที่นับว่าขีดฆ่าไปแล้วกี่ครั้ง และ $j$ หมายถึงตัวเลขน้อยสุดที่ยังไม่ถูกขีดฆ่า

เนื่องจากจำนวนที่น้อยที่สุดที่ยังไม่ถูกขีดฆ่าต้องเป็นจำนวนเฉพาะอยู่แล้ว เพราะหลังจากขีดฆ่าไป จำนวนที่ไม่ใช่จำนวนเฉพาะที่มาก่อนจำนวนน้อยที่สุดที่ยังไม่ถูกขีดฆ่า ก็จะถูกขีดฆ่าไป เช่น $2$, $3$, $4$, $5$, $6$, $7$ หลังจากเริ่มขีดฆ่าพหุคูณของ $2$ จะเหลือเลข $3$, $5$, $6$, $7$ ขีดฆ่าพหุคูณของ $3$ จะเหลือ $5$, $7$ ขีดฆ่าพหุคูณของ $5$ จะเหลือเลข $7$ เป็นตัวสุดท้าย จะเห็นได้ว่าจำนวนที่น้อยที่สุดที่ยังไม่ถูกขีดฆ่า จะเป็นจำนวนเฉพาะเสมอ ดังนั้นไม่ต้องสนใจประโยคที่ว่า "ให้จำนวนนั้นคือ $P$ ( $P$ คือจำนวนเฉพาะ )"

ขั้นตอนการทำงาน

1. ถ้า Array ช่องที่ $j$ มีค่าเท่ากับ $1$ ให้ข้ามไปทำขั้นตอนที่ 6
2. ไล่จำนวนที่เป็นพหุคูณของ $j$ ที่น้อยกว่าหรือเท่ากับ $N$ และให้เลขนั้นคือเลข $i$ แล้วทำขั้นตอนที่ 2 ถึง 4 ให้ครบทุกตัว
3. ถ้า Array ช่องที่ $i$ มีค่าเท่ากับ $1$ ให้ $i$ มีค่าเพิ่มขึ้นเป็นเป็นพหุคูณของ $j$ ตัวถัดไป
4. ให้ $c$ มีค่าเพิ่มขึ้น $1$ และ กำหนดให้ค่าของ Array ช่องที่ $i$ มีค่าเท่ากับ $1$
5. ถ้า $c$ มีค่าเท่ากับ $K$ ให้ส่งออกค่า $i$ แล้วจบการทำงาน
6. เพิ่มค่า $j$ ให้มากขึ้น $1$ แล้วกลับไปทำขั้นตอนที่ 1

ตัวอย่างการทำงานของ $N = 7$ (ค่าในตารางแสดงถึงลำดับที่ถูกขีดฆ่า)

Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> alr(n+1);

    int c = 0, j = 2;
    while (1) {
        if (!alr[j]) {
            for (int i = j; i <= n; i += j) {
                if (!alr[i]) {
                    c++;
                    alr[i] = 1;
                    if (c == k) {
                        cout << i;
                        return 0;
                    }
                }
            }
        }
        j++;
    }
    return 0;
}