最小Smith数

/*
若一个合数的质因数分解式逐位相加之和等于其本身逐位相加的和，则称这个数为Smith数。
例如，4937775=3*5*5*65837，而3+5+5+6+5+8+3+7=42，
    4+9+3+7+7+7+5=42，所以493775是Smith数。给定一个正整数N,求大于n的最小Smith数
    01点14分

    输入描述：若干个case 每个case一行代表正整数N，输入0表示结束
    输出描述：大于N的最小Smith数

    输入样例：
    4937774
    0
    输出样例：
    4937775

*/

粘贴代码请粘贴前面的，后面只是方便观看，但是标点不对，网页自动转成中文标点了，内容都一样

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;


void Fenjie(int a,vector<int> &v)//用于分解质因数，a是需要分解的数，容器v是存储分解出的数字的数组
//设为引用因为后面需要用这个容器里面的内容，当然也可以定义一个指针函数
    {
        
     
        int i=2;//若分解的数小于等于2，则不会进入下面的循环
        for( i=2;i<=a;i++)//质因数至少要等于2，不能是1
        {
            if(a%i == 0)//这里思路是是只寻找当前最小的质因数，另一个因数递归调用这个函数再寻找最小的因数，最小的因数一定是质数
            break;//若找到则退出循环，i归零
        }
       v.push_back(i);//最小的因数存入容器里
       a=a/i;//这里更新a的值，变成另一个因数，
       //也就是下一次待分解的数。
       if (a>1)//作为递归入口（出口）,若a=1说明a更新之前本身就是一个质数，在上面循环里找到的最小质因数是它本身
       //这里不用！=1的原因是考虑如果一开始入的a=1，1/2<1,将执行递归，这是不对的，改成>号后将直接存入容器后结束函数
      {   Fenjie(a,v);//处理另一个因数
    
      }
       
    }


    int Smith(vector<int> &v)//找出大于n的最小Smith数，v是数组容器，用来提供给分解因数的函数调用，
    //待分解因数函数返回结果后进行逐位加法用
{
        int n;//n是输入测试数字的临时变量
        int sum;//sum是质因数逐位相加的和
        int sum1;//sum1是数字本身逐位相加
        int pow;//这个变量是用来探测这个数字有多少位，实际上它表示“这个数除以多少小数点会移到这一位右边”
        //这个数都是10的n次方
        vector<int> v1;//题目要求要有多组输入，v1用来保存输入样例
        for(int w=0;;w++)//这个循环用来满足题目多组输入要求，不必深究
    {
        scanf("%d",&n);
        if(n==0)
        {
            break;
        }
        v1.push_back(n);//把输入样例存入v1。注意break和push的顺序
       
    }
for(int q=0;q<v1.size();q++)//这是个大循环，也是用来满足题目，多组输入自然多组输出，可以自行屏蔽这一层循环
  {
     for(int i=v1[q]+1;;i++)//这个循环是核心算法需要，注意这里用的不是n了，而是数组里面的值，
     //这个循环是从比输入的数大1的数开始挨个试是不是Smith数，每次加1
     {
        sum1=0;//每次试数循环要把两个求和变量置零
        
        sum=0;
        for(pow=1;;pow=pow*10)//这个循环是为了确定数字有多少位。即使这个数除以pow的结果为它的最高位数
        {
            if(i/pow <10)//商小于10时目的已经达到，跳出循环，这个pow已经找到
            break;
        }
            int shang;//定义一个商变量，用来存放当前数字除以pow的结果
            int s;//用来村航经过处理后得到的这一位数字

        for(;pow >= 1;pow=pow/10)//这个循环用来求出每一位并且进行累加
        //pow每次循环缩小10倍，需要注意的是，这个=号必须要有，不然会少加个位数
        {
            
            shang=i/pow;//第一次商为高一位，以本例来看就是4，第二次是高两位49，以此类推
        
            s=shang-(shang/10)*10;//减掉商左边的高位，只留下最右边的一位，这里商先除以10小数点左移一位
            //因为是int类型，小数位自动丢弃，再乘以10，变成之前商整十数，如第二次的过程是49/10=4.9->4,4*10=40
            //减去这个整十数就是我们要得的那一位数了
            sum1=sum1+s;//把得到的数累加起来
        }

            //后面该求质因数的逐位求和了
         Fenjie(i,v);//调用分解质因数函数，i还是之前的i，本次试数循环还没完，
         //v再这个函数没调用之前是一个空的容器，由Smith函数参数提供，调用后存储了i的所有质因数
         
     

         for(int m=0;m<v.size();m++)//遍历i的所有质因数
       {
          for(pow=1;;pow=pow*10)//因数的位数还是不确定，故还得重复上面的步骤确定位数
        {
            if(v[m]/pow <10)
            break;
        }
            

        for(;pow >= 1;pow=pow/10)//原理和上面一样
        {
            
            shang=v[m]/pow;
        
            s=shang-(shang/10)*10;
            sum=sum+s;
        }
       }
       v.clear();//这里要先清空容器，因为这里用的是引用，上一次调用容器里面依然存在原来的数据，清空后再进行下一次试数
       if(sum == sum1)//若相等则找到，返回i即可
       {
           return i;
          
       }
     }//试数循环结束括号
  }//这是多组输出循环后括号   
}//函数结束括号
int main()
{
    vector<int> v;
   
  printf("%d\n",Smith(v));
    system("pause");
}