The Ternary Goldbach Conjecture asserts that any odd integer greater than 7 can be represented as the sum of three prime numbers. While proven for sufficiently large numbers, verifying this for smaller integers requires an effiicent computational approach. Given an odd integer n (9 < n < 20,000), our objective is to find a triplet of primes (p1, p2, p3) such that p1 + p2 + p3 = n, prioritizing the smallest possible values for p1 and subsequently p2.

Algorithm Strategy

Directly checking primality for each iteration is computationally expensive. Instead, we utilize the Sieve of Eratosthenes to precompute all primes up to n. Once we have a list of prime numbers, we iterate through the list to find the combination that satisfies the sum requirement while respecting the lexicographical order constraint.

Implementation

import sys

def get_primes(limit):
    """Generates a list of primes up to limit using Sieve of Eratosthenes."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(limit**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
    return [x for x, val in enumerate(is_prime) if val]

def solve_goldbach(target):
    primes = get_primes(target)
    # Use a set for O(1) lookup performance
    prime_set = set(primes)
    
    # Iterate through possible combinations
    for i in range(len(primes)):
        p1 = primes[i]
        for j in range(i, len(primes)):
            p2 = primes[j]
            p3 = target - p1 - p2
            
            # Since p1 <= p2 <= p3, we stop if p3 is smaller than p2
            if p3 < p2:
                break
            
            if p3 in prime_set:
                return p1, p2, p3

# Execution
n = int(sys.stdin.readline())
result = solve_goldbach(n)
if result:
    print(f"{result[0]} {result[1]} {result[2]}")

The implemantation optimizes the search by nested looping. By pre-sorting the primes and enforcing the cnodition p1 ≤ p2 ≤ p3, we ensure the first valid triplet discovered is the lexicographically smallest. The search space is further pruned by calculating the third prime candidate as p3 = n - p1 - p2 and checking its existence in a hash set, significantly reducing the complexity compared to a naive triple-nested loop.