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

Phân tích Goldbach

Viết một số chẵn thành tổng của hai số nguyên tố, với số nguyên tố thứ nhất nhỏ nhất có thể.

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

  • Viết hàm kiểm tra số nguyên tố bằng phép chia thử, dừng ở √n
  • Duyệt các ứng viên theo thứ tự tăng dần và dừng ở kết quả đầu tiên
  • Trả về cặp số theo đúng thứ tự yêu cầu

Đề bài

Xem bản gốc (English)

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ụ

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

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

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.