Wu Yudong's Blog

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。

只有11个素数，无论从左往右还是从右往左逐一截去数字，剩下的仍然都是素数，求这些数的和。

注意：2、3、5和7不被视为可截素数。

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

Answer:748317

Completed on Fri, 26 Jul 2013, 19:09