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）acutus (mail: acutus@126.com)
// 博客地址：http://www.cnblogs.com/acutus/
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h> bool isprim(int n)
{
int i=;
if(n==) return false;
for(; i*i<=n; i++)
{
if(n%i==) return false;
}
return true;
} bool truncatable_prime(int n)
{
int i,j,t,flag=;
char s[];
int sum=;
sprintf(s,"%d",n);
int len=strlen(s); if(!isprim(s[]-'') || !isprim(s[len-]-'')) return false; for(i=; i<len-; i++)
{
t=s[i]-'';
if(t== || t== || t== || t== || t== || t==) return false;
} for(i=; i<len-; i++)
{
for(j=i; j<len-; j++)
{
sum+=s[j]-'';
sum*=;
}
sum+=s[j]-'';
if(!isprim(sum)) return false;
sum=;
}
j=len-;
i=;
while(j>i)
{
for(i=; i<j; i++)
{
sum+=s[i]-'';
sum*=;
}
sum+=s[i]-'';
if(!isprim(sum)) return false;
sum=;
i=;
j--;
}
return true;
} int main()
{
int sum,count;
sum=count=;
int i=;
while()
{
if(isprim(i) && truncatable_prime(i))
{
count++;
sum+=i;
//printf("%d\n",i);
}
i=i+;
if(count==) break;
}
printf("%d\n",sum);
return ;
}
|
Answer:
|
748317 |