Đề bài
Số nguyên tố sinh đôi là hai số nguyên tố hơn kém nhau 2 đơn vị, chẳng hạn 11 và 13, hay 17 và 19. Hãy tìm mọi cặp như vậy mà số lớn hơn trong cặp không vượt quá limit.
Hãy viết twin_primes(limit).
Với giới hạn lớn, hãy dùng sàng để tìm tất cả số nguyên tố một lượt, thay vì kiểm tra từng số riêng lẻ.
Đầu vào
limit: Giá trị lớn nhất mà số nguyên tố lớn hơn trong cặp được phép có.
Đầu ra
Trả về danh sách các cặp [p, p + 2] trong đó cả hai số đều nguyên tố và p + 2 ≤ limit, sắp xếp theo p tăng dần. Nếu không có cặp nào, trả về danh sách rỗng.
Ràng buộc
0 ≤ limit ≤ 10^6
Ví dụ
Đầu vào:
limit = 20
Kết quả mong đợi:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
Đầu vào:
long long limit = 20;
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
Đầu vào:
long limit = 20;
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
Giải thích
Các số nguyên tố không vượt quá 20 là 2, 3, 5, 7, 11, 13, 17, 19; những cặp hơn kém nhau 2 cho ra [[3, 5], [5, 7], [11, 13], [17, 19]].
Đầu vào:
limit = 6
Kết quả mong đợi:
expected = [
[3, 5]
]
Đầu vào:
long long limit = 6;
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
Đầu vào:
long limit = 6;
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {3, 5}
};
Giải thích
3 và 5 đều nguyên tố và 5 ≤ 6, nhưng 7 vượt quá giới hạn, nên chỉ có [[3, 5]].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Sàng tìm mọi số nguyên tố đến 10^6 nhanh hơn nhiều so với kiểm tra từng số.
Gợi ý 2
Sau đó kiểm tra mọi p thỏa mãn p + 2 ≤ limit.
Gợi ý 3
Cặp đầu tiên là (3, 5), nên mọi giới hạn nhỏ hơn 5 đều cho danh sách rỗng.
Độ phức tạp mong đợi
thời gian O(limit log log limit), bộ nhớ phụ O(limit)
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.