# 工学1号馆

home

## Project Euler 37–Truncatable primes

Wu Yudong    August 20, 2018     欧拉计划   555

Truncatable primes

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

3797有着奇特的性质。不仅它本身是一个素数，而且如果从左往右逐一截去数字，剩下的仍然都是素数：3797、797、97和7；同样地，如果从右往左逐一截去数字，剩下的也依然都是素数：3797、379、37和3。

//（Problem 37）Truncatable primes
// Completed on Thu, 31 Oct 2013, 13:12
// Language: C
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>

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

bool truncatable_prime(int n)
{
int i, j, t, flag = 1;
char s[6];
int sum = 0;
sprintf(s, "%d", n);
int len = strlen(s);

if (!isprim(s[0] - '0') || !isprim(s[len - 1] - '0'))
return false;

for (i = 1; i < len - 1; i++) {
t = s[i] - '0';
if (t == 0 || t == 2 || t == 4 || t == 6 || t == 5 || t == 8)
return false;
}

for (i = 1; i < len - 1; i++) {
for (j = i; j < len - 1; j++) {
sum += s[j] - '0';
sum *= 10;
}
sum += s[j] - '0';
if (!isprim(sum))
return false;
sum = 0;
}
j = len - 1;
i = 0;
while (j > i) {
for (i = 0; i < j; i++) {
sum += s[i] - '0';
sum *= 10;
}
sum += s[i] - '0';
if (!isprim(sum))
return false;
sum = 0;
i = 0;
j--;
}
return true;
}

int main()
{
int sum, count;
sum = count = 0;
int i = 13;
while (1) {
if (isprim(i) && truncatable_prime(i)) {
count++;
sum += i;
//printf("%d\n",i);
}
i = i + 2;
if (count == 11)
break;
}
printf("%d\n", sum);
return 0;
}