[ create a new paste ] login | about

Link: http://codepad.org/ZJHBDLKC    [ raw code | fork ]

C, pasted on May 7:
/*
    素数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;
}


Create a new paste based on this one


Comments: