Đề bài
Các số nguyên tố theo thứ tự là 2, 3, 5, 7, 11, 13, … Cho vị trí n, hãy trả về số nguyên tố ở vị trí đó. Với n nhỏ, bạn có thể kiểm tra từng số một; nhưng với đầu vào lớn, dùng sàng (sieve) trên một khoảng đủ rộng sẽ nhanh hơn nhiều.
Hãy viết nth_prime(n).
Đầu vào
n: Vị trí trong dãy số nguyên tố, bắt đầu từ 1.
Đầu ra
Trả về số nguyên tố thứ n. nth_prime(1) bằng 2.
Ràng buộc
1 ≤ n ≤ 100,000
Ví dụ
Đầ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
Dãy số nguyên tố bắt đầu bằng 2, 3, 5, 7, 11, 13, nên số thứ sáu là 13.
Đầ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
Số nguyên tố đầu tiên là 2.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đếm số nguyên tố khi tìm được cũng được, nhưng kiểm tra từng số bằng phép chia thử sẽ chậm khi n lớn.
Gợi ý 2
Số nguyên tố thứ 100,000 nhỏ hơn 1,300,000, nên một cái sàng cỡ đó là đủ.
Gợi ý 3
Nếu sàng hóa ra quá nhỏ, hãy nhân đôi kích thước và thử lại.
Độ phức tạp mong đợi
thời gian O(m log log m), bộ nhớ phụ O(m), với m là kích thước sàng
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.