Prime Pairs With Target Sum - Practice Coding Problems

Prime Pairs With Target Sum - Problem

You are given an integer n. We say that two integers x and y form a prime number pair if:

1 <= x <= y <= n
x + y == n
x and y are prime numbers

Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.

Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.

Input & Output

Example 1 — Basic Case

$ Input: n = 12

› Output: [[5,7]]

💡 Note: The prime numbers ≤ 12 are: 2, 3, 5, 7, 11. We need pairs that sum to 12: 5 + 7 = 12, and both 5 and 7 are prime, so return [[5,7]].

Example 2 — Multiple Pairs

$ Input: n = 20

› Output: [[3,17],[7,13]]

💡 Note: Prime numbers ≤ 20: 2, 3, 5, 7, 11, 13, 17, 19. Valid pairs summing to 20: 3+17=20 and 7+13=20. Both pairs have prime numbers.

Example 3 — No Valid Pairs

$ Input: n = 4

› Output: []

💡 Note: Only primes ≤ 4 are 2 and 3. We need pairs summing to 4: 2+2=4, but we need x ≤ y and distinct pairs. No valid pairs exist.

Constraints

2 ≤ n ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n, find prime pairs [x,y] where x+y=n

Process

Identify all primes ≤ n and check valid pairs

Output

Return sorted list of prime pairs

Key Takeaway

🎯 Key Insight: Use Sieve of Eratosthenes to precompute primes, then efficiently check complementary pairs

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to precompute all prime numbers using the Sieve of Eratosthenes, then check pairs efficiently. Best approach uses sieve preprocessing for O(n log log n) time complexity and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × √n)	O(1)	Check all possible pairs and test primality for each number
Sieve of Eratosthenes	O(n log log n)	O(n)	Precompute all primes using sieve, then find pairs efficiently

Brute Force — Algorithm Steps

Iterate through all x from 2 to n/2
Calculate y = n - x
Check if both x and y are prime
If both prime and x <= y, add [x, y] to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Test x=2

Check if 2 and n-2 are both prime

Test x=3

Check if 3 and n-3 are both prime

Continue

Test all x up to n/2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int num) {
    if (num < 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    
    printf("[");
    bool first = true;
    for (int x = 2; x <= n / 2; x++) {
        int y = n - x;
        if (x <= y && isPrime(x) && isPrime(y)) {
            if (!first) printf(",");
            printf("[%d,%d]", x, y);
            first = false;
        }
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × √n)

For each of n numbers, check primality in O(√n) time

✓ Linear Growth

Space Complexity

O(1)

Only uses variables for iteration and result storage

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler