โจทย์
จำนวนเฉพาะเรียงตามลำดับได้แก่ 2, 3, 5, 7, 11, 13, … เมื่อกำหนดลำดับที่ n ให้คืนค่าจำนวนเฉพาะที่อยู่ในลำดับนั้น การทดสอบทีละจำนวนใช้ได้ดีเมื่อ n มีค่าน้อย แต่สำหรับอินพุตที่ใหญ่ขึ้น การใช้ตะแกรง (sieve) บนช่วงที่กว้างพอจะเร็วกว่ามาก
จงเขียนฟังก์ชัน nth_prime(n)
อินพุต
n: ลำดับที่ในรายการจำนวนเฉพาะ เริ่มนับจาก 1
เอาต์พุต
คืนค่าจำนวนเฉพาะตัวที่ n โดย nth_prime(1) คือ 2
เงื่อนไข
1 ≤ n ≤ 100,000
ตัวอย่าง
อินพุต:
n = 6
ผลลัพธ์ที่คาดหวัง:
expected = 13
อินพุต:
long long n = 6;
ผลลัพธ์ที่คาดหวัง:
long long expected = 13;
อินพุต:
long n = 6;
ผลลัพธ์ที่คาดหวัง:
long expected = 13;
คำอธิบาย
จำนวนเฉพาะเริ่มต้นด้วย 2, 3, 5, 7, 11, 13 ตัวที่หกจึงเป็น 13
อินพุต:
n = 1
ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
long long n = 1;
ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
long n = 1;
ผลลัพธ์ที่คาดหวัง:
long expected = 2;
คำอธิบาย
จำนวนเฉพาะตัวแรกคือ 2
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
การนับจำนวนเฉพาะไปเรื่อย ๆ ขณะที่หาเจอก็ใช้ได้ แต่การทดสอบทุกจำนวนด้วยการหารทดลองจะช้าเมื่อ n มีค่ามาก
คำใบ้ 2
จำนวนเฉพาะตัวที่ 100,000 มีค่าน้อยกว่า 1,300,000 ตะแกรงขนาดเท่านี้จึงเพียงพอ
คำใบ้ 3
ถ้าตะแกรงเล็กเกินไป ให้ขยายเป็นสองเท่าแล้วลองใหม่
ความซับซ้อนที่คาดหวัง
เวลา O(m log log m), หน่วยความจำเพิ่ม O(m) โดย m คือขนาดของตะแกรง
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน