# 工学1号馆

home

## Project Euler 49–Prime permutations

Wu Yudong    August 20, 2018     欧拉计划   558

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?

//（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;
}