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

Goldbach Partition

Write an even number as the sum of two primes, using the smallest possible first prime.

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

  • Write a trial-division prime test that stops at √n
  • Search candidates in increasing order and stop at the first hit
  • Return a pair in the required order

Đề bài

Xem bản dịch

Goldbach's conjecture says that every even number greater than 2 is the sum of two primes. It has never been proven, but it has been checked far beyond the numbers here. Often there are several ways: 28 = 5 + 23 = 11 + 17. Find the one whose smaller prime is as small as possible.

Implement goldbach_partition(n).

Trying p = 2, 3, 5, ... and testing whether n − p is prime finds the answer quickly, because a small p almost always works. Testing a number up to 10^9 for primality by trial division only needs divisors up to about 31,623.

Input

n: An even number greater than 2.

Output

Return [p, q] where p and q are primes, p + q = n, p ≤ q, and p is the smallest prime for which this works.

Ràng buộc

4 ≤ n ≤ 10^9, n is even

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 and 28 − 3 = 25 are not prime, but 28 − 5 = 23 is, so the answer is [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

The only option is 2 + 2, so the answer is [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

Try p = 2, 3, 4, ... and stop at the first p where both p and n − p are prime.

Gợi ý 2

A prime test only needs to try divisors up to the square root.

Gợi ý 3

Since you stop at the smallest p, p ≤ n − p comes for free.

Độ phức tạp mong đợi

O(k √n) time where k is the number of candidates tried, O(1) extra space

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.