Smith数的定义是各位数字之和与它的各个质因数（可以重复）的各位数字之和的总和相同的数，且不是素数。
题目本身是一道水题，数据尤其水。
下面的代码中加了一个优化：
先将所有询问按询问的数字升序排序，处理某个询问A时，如果结果是B，那么对其后询问值小于B的所有询问，都直接
给出答案为B。
例如：
23
24
25
26
27
0
在处理23时得到58，由于后面四个数都小于58，于是后面四个询问直接得到答案58而不必重复劳动。
最后再将所有询问按原先次序排序即可。
这样总体的平均时间复杂度介于O(m)和O(mlogm)之间，m为询问个数。
以下为代码。
时间：10毫秒
#include "stdio.h"#include "string.h"#include "stdlib.h"#include "math.h"int prime[1200];int Smith[5];struct query{ int ask,pos,ans;};int cmp_by_ask(const void *a,const void *b){ return (*(query *)a).ask-(*(query *)b).ask;}int cmp_by_pos(const void *a,const void *b){ return (*(query *)a).pos-(*(query *)b).pos;}void getPrime(){ memset(prime,0,sizeof(prime)); int i,j,sq,flag; prime[1]=2; prime[2]=3; prime[3]=5; prime[4]=7; prime[0]=4; for(i=11;i<=10100;i++){ if(!(i%2&&i%3&&i%5&&i%7))continue; sq=(int)(ceil(sqrt((double)i))+1); flag=1; for(j=11;j<=sq;j++){ if(i%j==0){ flag=0; break; } } if(flag){ prime[0]++; prime[prime[0]]=i; } }}int getSum(int x){ int sum=0; while(x){ sum+=(x%10); x/=10; } return sum;}int is_Smith(int x){ int sum1=0,sum2=getSum(x),i,j,cnt=0; for(i=1;i<=prime[0];i++){ while(x%prime[i]==0){ sum1+=getSum(prime[i]); cnt++; x/=prime[i]; } } if(x!=1){ sum1+=getSum(x); cnt++; } if((sum1==sum2)&&(cnt>1))return 1; else return 0;}int main(){ query p[50000]; int i,j,n,k,top; top=0; while(1){ scanf("%d",&p[top].ask); if(p[top].ask==0)break; p[top].pos=top; p[top].ans=-1; top++; } qsort(p,top,sizeof(p[0]),cmp_by_ask); getPrime(); //for(i=0;i