[C/C++] BOJ #1017 - Prime pairs

The problem “Prime Pairs” requires finding a pair of prime numbers for a given even number  n  such that the sum of the two prime numbers equals  n . This problem is a variation of the famous Goldbach’s conjecture, which states that every even integer greater than 2 can be expressed as the sum of two prime numbers.

Problem Description:
1. You are given an even number  n  ( \(n \geq 4\) ).
2. The task is to find two prime numbers  \(p_1\)  and  \(p_2\)  such that:

\[n = p_1 + p_2\]

3. If there are multiple pairs of prime numbers, the pair with the smallest  p_1  should be chosen.
4. If no such pair exists (though theoretically, it shouldn’t happen for even numbers  \(n \geq 4\) ), you should indicate that there is no solution.

Input:
The input consists of a single integer  n  ( \(n \geq 4\) ), where  n  is even.

Output:
• If a valid pair of primes  (\(p_1\), \(p_2\))  is found, output the pair in ascending order.
• If no such pair exists, output “No solution.”

Constraints:
• Efficient algorithms are necessary due to potential input size and computational limits when checking for prime numbers.

---

When I first encountered this problem, I initially thought it might involve “twin primes.” However, it’s not about prime pairs in that sense but about finding pairs of numbers whose sum is a prime. The problem involves determining whether, for a given even number  N , all the numbers can be paired such that each pair’s sum is a prime number. If it’s possible to pair them all, the task is to output the list of numbers that can pair with the first number.

 

number theory

While the difficulty level of this problem is rated as Platinum III, it is relatively easier—provided you are familiar with network flow algorithms.  Although it can be solved using a DFS algorithm, doing so would result in a time limit exceeded (TLE).

Key Insight for the Problem

The critical aspect of solving this problem is finding prime numbers quickly. Since the input list consists of 50 numbers, the task is to:
1. Select a second number that can pair with the first number (such that their sum is a prime).
2. Check whether the remaining numbers can also form valid prime pairs.

By precomputing a matching table, the maximum number of prime checks required is:

\[25 \times 49 = 1225\]

Given that the largest possible prime in this problem is less than 2000, the cost of each prime check is relatively low.

Algorithm Outline

The algorithm is straightforward:
1. The first number is fixed.
2. For each potential second number, check whether their sum is a prime.
3. If the sum is a prime, use a network flow algorithm to determine whether all remaining numbers can be paired into prime pairs.
4. If valid pairings are found, output the second number and repeat the process.

 

network flow algorithm

Here’s the source code I wrote to solve the problem:

//----------------------------------------------------------
//    baekjoon #1017 - Prime Pairs
//        - by Aubrey Choi
//        - created at 2019-05-20
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>

static unsigned char primes[] = {
    0xac,0x28,0x8a,0xa0,0x20,0x8a,0x20,0x28,    0x88,0x82,0x08,0x02,0xa2,0x28,0x02,0x80,
    0x08,0x0a,0xa0,0x20,0x88,0x20,0x28,0x80,    0xa2,0x00,0x08,0x80,0x28,0x82,0x02,0x08,
    0x82,0xa0,0x20,0x0a,0x20,0x00,0x88,0x22,    0x00,0x08,0x02,0x28,0x82,0x80,0x20,0x88,
    0x20,0x20,0x02,0x02,0x28,0x80,0x82,0x08,    0x02,0xa2,0x08,0x80,0x80,0x08,0x88,0x20,
    0x00,0x0a,0x00,0x20,0x08,0x20,0x08,0x0a,    0x02,0x08,0x82,0x82,0x20,0x0a,0x80,0x00,
    0x8a,0x20,0x28,0x00,0x22,0x08,0x08,0x20,    0x20,0x80,0x80,0x20,0x88,0x80,0x20,0x02,
    0x22,0x00,0x08,0x20,0x00,0x0a,0xa0,0x28,    0x80,0x00,0x20,0x8a,0x00,0x20,0x8a,0x00,
    0x00,0x88,0x80,0x00,0x02,0x22,0x08,0x02,    0x80,0x08,0x82,0x80,0x20,0x00,0x22,0x28,
    0x80,0x82,0x00,0x0a,0xa0,0x20,0x00,0x80,    0x28,0x82,0x20,0x20,0x08,0x02,0x00,0x80,
    0x02,0x08,0x08,0x20,0x08,0x02,0x02,0x20,    0x82,0xa0,0x20,0x00,0x02,0x08,0x00,0xa0,
    0x08,0x0a,0xa2,0x08,0x80,0x82,0x00,0x00,    0x00,0x00,0x82,0x20,0x20,0x00,0x80,0x00,
    0x02,0x80,0x28,0x82,0x80,0x28,0x08,0x80,    0x00,0x8a,0x22,0x08,0x80,0x00,0x08,0x08,
    0x80,0x20,0x82,0x80,0x08,0x88,0x00,0x20,    0x82,0x22,0x28,0x08,0x20,0x00,0x00,0x82,
    0x28,0x00,0x00,0x20,0x0a,0x20,0x00,0x0a,    0x20,0x20,0x08,0x82,0x00,0x00,0x82,0x28,
    0x00,0x02,0x08,0x80,0x80,0x00,0x80,0x00,    0x20,0x88,0xa2,0x00,0x02,0x20,0x08,0x02,
    0x00,0x28,0x00,0xa0,0x00,0x00,0x20,0x08,    0x08,0xa2
};
inline bool isprime(int p) { return (bool)((primes[p / 8] >> (p % 8)) & 1); }
char b[25], v[25], adj[25][26]; int n;
bool dfs(int s)
{
    v[s] = 1;
    for(int i = 1; i <= adj[s][0]; i++)
    {
        int t = adj[s][i];
        if(b[t] == -1 || (v[b[t]] == 0 && dfs(b[t])))
        {
            b[t] = s;
            return true;
        }
    }
    return false;
}
bool checkmatch(int s, int n)
{
    memset(b, 0xff, sizeof(b));
    b[s] = 0;
    for(int i = 1; i < n; i++)
    {
        memset(v, 0, sizeof(v));
        v[0] = 1;
        if(!dfs(i)) return false;
    }
    return true;
}
int main()
{
    int l[25], r[25], lcount = 1, rcount = 0, t, i, j;

    scanf("%d%d",&n,&l[0]);
    for(i=1;i<n;i++) { scanf("%d",&t); if((t+l[0])%2) r[rcount++]=t; else l[lcount++]=t; }
    if(lcount != rcount) { puts("-1"); return 0; }

    //    check primes between elements.
    for(i = 0; i < lcount; i++)
    {
        int count = 0;
        for(j = 0; j < lcount; j++)
        {
            if(isprime(l[i] + r[j])) adj[i][++count] = j;
        }
        adj[i][0] = count;
        if(!count) { puts("-1"); return 0; }
    }

    int ans[100], count = 0;
    for(i=1;i<=adj[0][0];i++)
    {
        int s = adj[0][i];
        if(checkmatch(s, lcount))
        {
            int last = count++;
            while(last > 0 && ans[last-1] > r[s])
            {
                ans[last] = ans[last-1];
                last--;
            }
            ans[last] = r[s];
        }
    }

    if(count == 0) { puts("-1"); return 0; }
    for(i = 0; i < count; i++) printf("%d ", ans[i]); putchar('\n');
}