Wu Yudong's Blog

Prime permutations

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

素数重排

公差为3330的三项等差序列1487、4817、8147在两个方面非常特别：其一，每一项都是素数；其二，两两都是重新排列的关系。

一位素数、两位素数和三位素数都无法构成满足这些性质的数列，但存在另一个由四位素数构成的递增序列也满足这些性质。

将这个数列的三项连接起来得到的12位数是多少？

//（Problem 49）Prime permutations
// Completed on Thu, 13 Feb 2014, 15:35
// Language: C
//**********************************************
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com/
//**********************************************
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
int a[1230];

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

int cmp(const void *a, const void *b)
{
    return (*(char*)a - *(char*)b);
}

void init()
{
    int i, j;
    i = 3;
    j = 1;
    a[0] = 2;
    while(j < 1230) {
        if(prim(i)) {
            a[j++] = i;
        }
        i += 2;
    }
}

bool judge(int a, int b, int c)
{
    char A[5], B[5], C[5];
    sprintf(A, "%d", a);
    qsort(A, 4, sizeof(char), cmp);
    sprintf(B, "%d", b);
    qsort(B, 4, sizeof(char), cmp);
    sprintf(C, "%d", c);
    qsort(C, 4, sizeof(char), cmp);
    if(strcmp(A, B)== 0 && strcmp(A, C) == 0)
        return true;
    return false;
}

void solve()
{
    int i, b, c, d;
    i = 0;
    init();
    while(a[i++] < 1000);
    for(; i < 1229; i++) {
        b = a[i];  c = a[i] + 3330;  d = a[i] + 6660; 
        if(d < 9999) {
            if(prim(b) && prim(c) && prim(d)) {
                if(judge(b, c, d)) {
                    printf("%d %d %d\n", b, c, d);
                }
            }
        }
    }
    
}

int main()
{
    solve();
    return 0;
}

Answer:296962999629

Completed on Thu, 13 Feb 2014, 15:35