1.先用筛法做出一个素数组。

 

2.求得prime factors and add the digit of each prime.

 

3.add the digit of the given number.

 

4.compare the two sum.

 

#include <iostream>
using namespace std;
int prm[100000];
int nn;
long s_num;
int prime(int a[],int n)
      {
          int i,j,k,x,num,*b;
          n++;
          n/=2;
          b=new int[(n+1)*2];
          a[0]=2;a[1]=3;num=2;
          for(i=1;i<=2*n;i++)
              b[i]=0;
          for(i=3;i&lt;=n;i+=3)
              for(j=0;j&lt;2;j++)
                  {
                  x=2*(i+j)-1;
                  while(b[x]==0)
                      {
                      a[num++]=x;
                      for(k=x;k&lt;=2*n;k+=x)
                          b[k]=1;
                      }
                  }
          return num;
      }
long d_sum(long os)
{
 long temp=os;
 long ans=0;
 while(temp!=0){
    ans+=temp%10;
    temp/=10;
    }
 return ans;
}
long is_Smith_num()
{
 long sum;
 long num=s_num+1;
 int j=1;
 while(1)
 {
        sum=d_sum(num);
  long p_sum=0;
  while(num!=1)
  {
   int i;
   for( i=0;i&lt;nn;i++)
   {
    if(num%prm[i]==0&&prm[i]!=s_num+j)
    {
     num=num/prm[i];
     p_sum+=d_sum(prm[i]);
     break;
    }
   }
   if(i==nn)
   {
    if(num!=s_num+j)
    p_sum+=d_sum(num);
    num=1;
   }
   if(p_sum>sum)
    num=1;
  }
  if(sum==p_sum)
   return s_num+j;
  else
  {
   j++;
   num=s_num+j;
  }  }
}
int main()
{
 nn=prime(prm,100000);
 while(cin &gt;&gt;s_num&&s_num)
 {
  cout&lt;&lt;is_Smith_num()&lt;&lt;endl;
 }
 return 0;
}