/*
素数3, 7, 109, 673は非凡な性質を持っている.
任意の2つの素数を任意の順で繋げると, また素数になっている.
例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である.
これは, このような性質をもつ4つの素数の集合の和の中で最小である.
任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の集合の和の中で最小のものを求めよ.
*/
#include <stdio.h>
#include <stdbool.h>
#define PRIMEN 10000
#define PRIMER 5 // 5つの素数の集合
#define PAIRN PRIMER
#define PAIRR 2 // 2つの素数をつなげる
bool isPrime(int num, int *primeList, int size) {
int i;
if( num < 2 ) return false;
if( num == 2 ) {
primeList[0] = 2;
return true;
}
if( num % 2 == 0 ) return false;
for( i = 0; i < size && primeList[i] != 0 && primeList[i] * primeList[i] <= num; i++ ) {
if( num % primeList[i] == 0 ) return false;
}
return true;
}
void primeList(int *prime, int size) {
int num;
int i = 1;
prime[0] = 2;
for( num = 3; ; num += 2 ) {
if( isPrime(num, prime, size) ) {
prime[i++] = num;
if( i == size ) return;
}
}
}
bool nextComb(int c[], int n, int r) {
int d, i;
for( d = r; d > 0; d-- ) {
if( c[d] < n - (r - d) ) break;
}
if( d == 0 ) return false;
c[d]++;
for( i = d + 1; i <= r; i++ ) {
c[i] = c[i - 1] + 1;
}
return true;
}
// num1が左
int cat(int num1, int num2) {
int tmp = num2;
while( tmp > 0 ) {
tmp /= 10;
num1 *= 10;
}
return num1 + num2;
}
int main(void) {
int prime[PRIMEN] = { 0 };
int primeComb[PRIMER + 1];
int combIdx[PAIRR + 1];
int sum = 0;
bool flag;
int i, j, k, l, m;
primeList(prime, PRIMEN);
for( i = PRIMER - 1; i < PRIMEN; i++ ) {
for( j = i - 1; j >= 3; j-- ) {
if( !isPrime(cat(prime[i], prime[j]), prime, PRIMEN) ||
!isPrime(cat(prime[j], prime[i]), prime, PRIMEN) ) {
continue;
}
for( k = j - 1; k >= 2; k-- ) {
if( !isPrime(cat(prime[k], prime[i]), prime, PRIMEN) ||
!isPrime(cat(prime[i], prime[k]), prime, PRIMEN) ||
!isPrime(cat(prime[k], prime[j]), prime, PRIMEN) ||
!isPrime(cat(prime[j], prime[k]), prime, PRIMEN) ) {
continue;
}
for( l = k - 1; l >= 1; l-- ) {
if( !isPrime(cat(prime[l], prime[i]), prime, PRIMEN) ||
!isPrime(cat(prime[i], prime[l]), prime, PRIMEN) ||
!isPrime(cat(prime[l], prime[j]), prime, PRIMEN) ||
!isPrime(cat(prime[j], prime[l]), prime, PRIMEN) ||
!isPrime(cat(prime[l], prime[k]), prime, PRIMEN) ||
!isPrime(cat(prime[k], prime[l]), prime, PRIMEN) ) {
continue;
}
for( m = l - 1; m >= 0; m-- ) {
if( !isPrime(cat(prime[m], prime[i]), prime, PRIMEN) ||
!isPrime(cat(prime[i], prime[m]), prime, PRIMEN) ||
!isPrime(cat(prime[m], prime[j]), prime, PRIMEN) ||
!isPrime(cat(prime[j], prime[m]), prime, PRIMEN) ||
!isPrime(cat(prime[m], prime[k]), prime, PRIMEN) ||
!isPrime(cat(prime[k], prime[m]), prime, PRIMEN) ||
!isPrime(cat(prime[m], prime[l]), prime, PRIMEN) ||
!isPrime(cat(prime[l], prime[m]), prime, PRIMEN) ) {
continue;
}
printf("{%d, %d, %d, %d, %d}\n",
prime[m], prime[l], prime[k], prime[j], prime[i]);
printf("%d\n",
prime[m] + prime[l] + prime[k] + prime[j] + prime[i]);
}
}
}
}
}
return 0;
}