工学1号馆

home

Project Euler 37–Truncatable primes

Wu Yudong    August 20, 2018     欧拉计划   517   

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

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

Comments

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