ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Goldbach Partition

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

สิ่งที่คุณจะได้เรียนรู้

  • 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

โจทย์

ดูฉบับแปล

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.

เงื่อนไข

4 ≤ n ≤ 10^9, n is even

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
n = 28

ผลลัพธ์ที่คาดหวัง:
expected = [5, 23]
อินพุต:
long long n = 28;

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {5, 23};
อินพุต:
long n = 28;

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {5, 23};

คำอธิบาย

28 − 2 = 26 and 28 − 3 = 25 are not prime, but 28 − 5 = 23 is, so the answer is [5, 23].

ตัวอย่างที่ 2
อินพุต:
n = 4

ผลลัพธ์ที่คาดหวัง:
expected = [2, 2]
อินพุต:
long long n = 4;

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {2, 2};
อินพุต:
long n = 4;

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {2, 2};

คำอธิบาย

The only option is 2 + 2, so the answer is [2, 2].

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

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

คำใบ้ 2

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

คำใบ้ 3

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

ความซับซ้อนที่คาดหวัง

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

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก