作者在 2011-11-08 22:33:30 发布以下内容
题目描述：
据鹏鹏说，有一种数叫“菊花数”，是亚历山大东征印度时发明的；一个菊花数的每一位都是素数，并且如果在这个数的中间任意位置断开，分成的两个数都是素数。好了，现在鹏鹏问你，他给你一个数N，那么在1——N这些数中，有多少个菊花数？
数据范围：
t <= 10 ，n <= 10 ^ 9
输入格式：
第一行一个正整数T，表示有T组测试数据。
之后T行每行一个数，即N。
输出格式：
对于每组测试数据输出一个数，即答案。每个答案一行。
样例输入：
1
10
样例输出：
4
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#define GOLEFT 0
#define GORIGHT 1
int is_prime(int x)
{
int i;
if(x<4)
{
if(x==0||x==1) return 0;
}
for (i=2; i<=(int)sqrt(x); i++)
{
if(x%i==0) return 0;
}
return 1;
}
void change_p(int *p,int Long)
{
int temp,i,up;
up=Long;
for(i=0;i<Long/2;i++)
{
temp=p[i];
p[i]=p[up];
p[up]=temp;
up--;
}
//return p;
}
int maxture_aNum(int *p,int flag,int command,int Long)
{
int Num=0;
int i;
if(command==0)
{
for(i=0;i<=flag;i++)
{
Num=Num*10+p[i];
}
}
else if(command==1)
{
if(flag+1==Long-1) return p[flag+1];
else
{
for(i=flag+1;i<Long;i++)
{
Num=Num*10+p[i];
}
}
}
return Num;
}
int is_special(int x)
{
int y=x;
int num;
int p[10]={0};
int j, i=0;
//int test;
do
{
num=y%10;
if(!is_prime(num)) return 0;
p[i]=num;
i++;
y=y/10;
} while (y>0);
change_p(p,i-1);
if(i>2)
{
for (j=0; j<i-1; j++)
{
/*
*test=maxture_aNum(p,j,GOLEFT,i);
*if(!is_prime(test)) return 0;
*test=maxture_aNum(p,j,GORIGHT,i);
*if(!is_prime(test)) return 0;
*/
if(!(is_prime(maxture_aNum(p,j,GOLEFT,i)))) return 0;
if(!(is_prime(maxture_aNum(p,j,GORIGHT,i)))) return 0;
}
}
return 1;
}
void find_special(int up)
{
int sum=0;
int i;
for(i=1;i<=up;i++)
{
sum+=is_special(i);
}
printf("%d\n",sum);
}
int main()
{
int num,N[10];
int i;
scanf("%d",&num);
if(num>10) exit(-1);
for (i=0;i<num;i++ )
{
scanf("%d",&N[i]);
if (N[i]>(int)pow(10,9))exit(-1);
find_special(N[i]);
}
/*
*int i;
*for(i=1;i<1000;i++)
*{
* printf("%d\t%d\n",i,is_special(i));
*}
*/
return 0;
}
#include <math.h>
#include <stdio.h>
#define GOLEFT 0
#define GORIGHT 1
int is_prime(int x)
{
int i;
if(x<4)
{
if(x==0||x==1) return 0;
}
for (i=2; i<=(int)sqrt(x); i++)
{
if(x%i==0) return 0;
}
return 1;
}
void change_p(int *p,int Long)
{
int temp,i,up;
up=Long;
for(i=0;i<Long/2;i++)
{
temp=p[i];
p[i]=p[up];
p[up]=temp;
up--;
}
//return p;
}
int maxture_aNum(int *p,int flag,int command,int Long)
{
int Num=0;
int i;
if(command==0)
{
for(i=0;i<=flag;i++)
{
Num=Num*10+p[i];
}
}
else if(command==1)
{
if(flag+1==Long-1) return p[flag+1];
else
{
for(i=flag+1;i<Long;i++)
{
Num=Num*10+p[i];
}
}
}
return Num;
}
int is_special(int x)
{
int y=x;
int num;
int p[10]={0};
int j, i=0;
//int test;
do
{
num=y%10;
if(!is_prime(num)) return 0;
p[i]=num;
i++;
y=y/10;
} while (y>0);
change_p(p,i-1);
if(i>2)
{
for (j=0; j<i-1; j++)
{
/*
*test=maxture_aNum(p,j,GOLEFT,i);
*if(!is_prime(test)) return 0;
*test=maxture_aNum(p,j,GORIGHT,i);
*if(!is_prime(test)) return 0;
*/
if(!(is_prime(maxture_aNum(p,j,GOLEFT,i)))) return 0;
if(!(is_prime(maxture_aNum(p,j,GORIGHT,i)))) return 0;
}
}
return 1;
}
void find_special(int up)
{
int sum=0;
int i;
for(i=1;i<=up;i++)
{
sum+=is_special(i);
}
printf("%d\n",sum);
}
int main()
{
int num,N[10];
int i;
scanf("%d",&num);
if(num>10) exit(-1);
for (i=0;i<num;i++ )
{
scanf("%d",&N[i]);
if (N[i]>(int)pow(10,9))exit(-1);
find_special(N[i]);
}
/*
*int i;
*for(i=1;i<1000;i++)
*{
* printf("%d\t%d\n",i,is_special(i));
*}
*/
return 0;
}
