Prime Pair with Target Sum

JavaView on GFG

Intuition

Find all pairs of primes that sum to a given target (Goldbach-style). Sieve + pair finding.

Algorithm

1Sieve of Eratosthenes up to target. For each prime p <= target/2: if target-p is also prime: output pair.

Common Pitfalls

•Two primes summing to even number: one must be 2 or both odd. Sieve to target then linear scan.

Prime Pair with Target Sum.java

Java

// Approach: Sieve to find all primes up to n. Two pointer on prime list to find pairs summing to target.
// Time: O(n log log n) Space: O(n)
class Solution {
    public static ArrayList<Integer> getPrimes(int n) {
        int[] prime = new int[n + 1];
        prime[0] = prime[1] = 1;
        ArrayList<Integer> ans = new ArrayList<Integer>();
        
        for(int i = 2; i * i <= n; i++)
        {
            if(prime[i] == 0)
            {
                for(int j = i * i; j <= n; j += i)
                    prime[j] = 1;
            }
        }
        
        for(int i = 2; i <= n / 2; i++)
        {
            if(prime[i] == 0 && prime[n - i] == 0)
            {
                ans.add(i);
                ans.add(n - i);
                return ans;
            }
        }
        
        ans.add(-1);
        ans.add(-1);
        return ans;
    }
}

Was this solution helpful?