ตระแกรงร่อนของอีราโทสเธเนส เป็นอัลกอริทึมที่ให้หาจำนวนเฉพาะจนถึงจำนวนนับ N วิธีการมีดังนี้

1.        เขียนจำนวนนับตั้งแต่ 2 จนถึง N ทั้งหมด

2.        หาจำนวนที่น้อยที่สุดที่ยังไม่ถูกขีดค่า และเราให้จำนวนนั้นคือ P (P คือจำนวนเฉพาะ)

3.        ขีดค่าจำนวนที่เป็นพหุคูณของ P ทุกตัวที่ยังไม่ถูกขีดค่า

4.        ถ้ายังคงมีจำนวนนับที่ยังไม่ถูกขีดค่า ให้กลับไปทำขั้นตอนที่ 2

โจทย์

จงเขียนโปรแกรมที่รับจำนวนเต็ม N, K ให้หาว่า จำนวนตัวที่ K ที่ถูกขีดค่า คือจำนวนใด

ข้อมูลนำเข้า

บรรทัดแรก จำนวนเต็ม N และ K โดยที่ (2 <= K < N <= 1,000)

ข้อมูลส่งออก

บรรทัดแรก จำนวนตัวที่ K ที่ถูกขีดค่านับแต่เริ่มต้นอัลกอริทึม

อธิบายตัวอย่างที่สาม (ด้านล่าง)

ลำดับจำนวนตัวเลขที่ถูกขีดค่าคือ

2, 4, 6, 8, 10, 3, 9, 5 และ 7

และจำนวนที่ 7 ที่ถูกขีดค่าคือ 9

ที่มา: COCI 2008/2009, Contest #2 – November 15, 2008