ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Nth Prime

Return the nth prime number, counting 2 as the first.

สิ่งที่คุณจะได้เรียนรู้

  • Generate primes in order
  • Choose a sieve size large enough for the answer
  • Compare trial division with a sieve

โจทย์

ดูฉบับแปล

The primes in order are 2, 3, 5, 7, 11, 13, … Given a position n, return the prime at that position. Testing numbers one by one works for small n; for the larger inputs a sieve over a range that is big enough is much faster.

Implement nth_prime(n).

Input

n: The position in the list of primes, starting at 1.

Output

Return the nth prime. nth_prime(1) is 2.

เงื่อนไข

1 ≤ n ≤ 100,000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 6

ผลลัพธ์ที่คาดหวัง:
expected = 13
อินพุต:
long long n = 6;

ผลลัพธ์ที่คาดหวัง:
long long expected = 13;
อินพุต:
long n = 6;

ผลลัพธ์ที่คาดหวัง:
long expected = 13;

คำอธิบาย

The primes start 2, 3, 5, 7, 11, 13, so the sixth one is 13.

ตัวอย่างที่ 2
อินพุต:
n = 1

ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
long long n = 1;

ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
long n = 1;

ผลลัพธ์ที่คาดหวัง:
long expected = 2;

คำอธิบาย

The first prime is 2.

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

Counting primes as you find them works, but testing every number by trial division gets slow for large n.

คำใบ้ 2

The 100,000th prime is below 1,300,000, so a sieve of that size is enough.

คำใบ้ 3

If your sieve turns out too small, double it and try again.

ความซับซ้อนที่คาดหวัง

O(m log log m) time, O(m) extra space, where m is the sieve size

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก