Đề bài
Giả thuyết Goldbach phát biểu rằng mọi số chẵn lớn hơn 2 đều là tổng của hai số nguyên tố. Giả thuyết này chưa từng được chứng minh, nhưng đã được kiểm chứng với những số lớn hơn rất nhiều so với các số trong bài. Thường có nhiều cách viết: 28 = 5 + 23 = 11 + 17. Hãy tìm cách viết có số nguyên tố nhỏ hơn là nhỏ nhất.
Hãy viết goldbach_partition(n).
Thử lần lượt p = 2, 3, 5, ... và kiểm tra xem n − p có nguyên tố không sẽ cho ra đáp án rất nhanh, vì gần như lúc nào cũng có một p nhỏ thỏa mãn. Để kiểm tra tính nguyên tố của một số đến 10^9 bằng phép chia thử, bạn chỉ cần thử các ước đến khoảng 31,623.
Đầu vào
n: Một số chẵn lớn hơn 2.
Đầu ra
Trả về [p, q] với p và q là số nguyên tố, p + q = n, p ≤ q, và p là số nguyên tố nhỏ nhất thỏa mãn điều này.
Ràng buộc
4 ≤ n ≤ 10^9, n chẵn
Ví dụ
Đầu vào:
n = 28
Kết quả mong đợi:
expected = [5, 23]
Đầu vào:
long long n = 28;
Kết quả mong đợi:
std::vector<long long> expected = {5, 23};
Đầu vào:
long n = 28;
Kết quả mong đợi:
long[] expected = new long[] {5, 23};
Giải thích
28 − 2 = 26 và 28 − 3 = 25 không phải số nguyên tố, nhưng 28 − 5 = 23 thì có, nên kết quả là [5, 23].
Đầu vào:
n = 4
Kết quả mong đợi:
expected = [2, 2]
Đầu vào:
long long n = 4;
Kết quả mong đợi:
std::vector<long long> expected = {2, 2};
Đầu vào:
long n = 4;
Kết quả mong đợi:
long[] expected = new long[] {2, 2};
Giải thích
Chỉ có một cách là 2 + 2, nên kết quả là [2, 2].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Thử p = 2, 3, 4, ... và dừng ở p đầu tiên mà cả p lẫn n − p đều là số nguyên tố.
Gợi ý 2
Hàm kiểm tra số nguyên tố chỉ cần thử các ước đến căn bậc hai.
Gợi ý 3
Vì bạn dừng ở p nhỏ nhất, điều kiện p ≤ n − p tự nhiên được thỏa mãn.
Độ phức tạp mong đợi
thời gian O(k √n) với k là số ứng viên đã thử, bộ nhớ phụ O(1)
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.