Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Nth Prime

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

1 ≤ n ≤ 100,000

Ví dụ

Ví dụ 1
Đầu vào:
n = 6

Kết quả mong đợi:
expected = 13
Đầu vào:
long long n = 6;

Kết quả mong đợi:
long long expected = 13;
Đầu vào:
long n = 6;

Kết quả mong đợi:
long expected = 13;

Giải thích

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

Ví dụ 2
Đầu vào:
n = 1

Kết quả mong đợi:
expected = 2
Đầu vào:
long long n = 1;

Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long n = 1;

Kết quả mong đợi:
long expected = 2;

Giải thích

The first prime is 2.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.