工学1号馆

home

Project Euler 49–Prime permutations

Wu Yudong    August 20, 2018     欧拉计划   538   

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

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)