Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Số nguyên tố sinh đôi

Liệt kê mọi cặp số nguyên tố sinh đôi (p, p + 2) không vượt quá một giới hạn.

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

  • Đánh dấu các số nguyên tố đến một giới hạn bằng sàng
  • Tìm các số nguyên tố cách nhau 2 đơn vị
  • Xử lý giới hạn quá nhỏ để có cặp nào

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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]].

Ví dụ 2
Đầ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.

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.