[C/C++] Project Euler #60 - Prime Pair Sets

This is the first time I’m tackling a problem with a difficulty level of 20%.

Although it’s called a prime pair, there isn’t really any deep mathematical concept involved.

For example, if we take the two prime numbers 3 and 7, and simply concatenate them to form 37 and 73, and if both of these numbers are also prime, then (3, 7) is considered a prime pair.

Such prime pairs exist infinitely, but they are not very frequent.

---

prime number combinations

To solve this problem, it was important to decide whether to use memory to store the relevant sets. Doing so would require a very complex data structure, so I used a bit of a trick.

First, I pre-stored the prime numbers that would be used as building blocks for concatenation, and used a separate library to check whether the resulting concatenated numbers were prime. I also used a static variable called min to ensure that if the estimated value is larger than the current minimum value found, the program would stop processing further.

Even with this approach, it takes quite a bit of time. I do want to rewrite it with a better algorithm someday, but for now, I’ve decided to leave it as is.

Below is the source code.

//------------------------------------------------
//    Project Euler #60 - Prime Pair Sets
//        - by Aubrey Choi
//        - created at 2015-09-29
//------------------------------------------------
#include <stdio.h>
#include <time.h>
#include "isprime.h"

#define    N    5
#define    LIMIT    2000

int getminsum(int primes[], int pcount, int pset[][2], int n, int s, int sum)
{
    static int min = 0x7fffffff;

    if( n >= N ) return sum;
    for( int i = s ; i < pcount ; i++ )
    {
        if( sum+primes[i]*(N-n) >= min ) break;
        int c = 10;
        while( primes[i] >= c ) c *= 10;
        bool find = true;
        for( int j = 0 ; j < n ; j++ )
        {
            int t;
            t = pset[j][0]*c+primes[i];
            if( !isPrime(t) ) { find = false; break; }
            t = primes[i]*pset[j][1]+pset[j][0];
            if( !isPrime(t) ) { find = false; break; }
        }
        if( find == false ) continue;
        pset[n][0] = primes[i];
        pset[n][1] = c;
        int t = getminsum(primes, pcount, pset, n+1, i+1, sum+primes[i]);
        if( t < min ) min = t;
    }
    return min;
}

void solve1()
{
    static int primes[LIMIT];
    int pcount = 0;
    
    primes[pcount++] = 3;
    primes[pcount++] = 5;
    primes[pcount++] = 7;
    for( int p = 11 ; pcount < LIMIT ; p += 2 )
    {
        bool isPrime = true;
        for( int i = 0 ; primes[i]*primes[i] <= p ; i++ )
        {
            if( (p%primes[i]) == 0 ) { isPrime = false; break; }
        }
        if( isPrime ) primes[pcount++] = p;
    }

    int pset[5][2];
    int minsum = getminsum(primes, LIMIT, pset, 0, 0, 0);

    printf("Ans = %d\n", minsum);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}