题目：给定一个正整数x，找到一个最小的正整数y，使得y的每一位相乘，最后值等于x
思路：对x进行分解成多个数字相乘，然后把这些数字从小打到排序，最后组装成数字就得到最小的正整数y。
特殊情况：
1、如果x是大于10的质数或者x的因子中有大于10的质数，那么输入不合法！因为题目是要求y的每一位相乘，这样每一位的范围就是0~9，如果x是大于10的质数或者x的因子中有大于10的质数，那么x的因子中必定存在大于10的数，不满足条件！
2、如果输入的数小于10，则压入1和本身，这样得到的数是最小的。
3、输入的数进过多次分解之后剩下的数如果小于10，则压入本身，这个和情况2是有区别的。
代码如下：
//是否是质数
bool isZhiShu(int num){
int a = 0;
for (int i = 2; i < num; i++)
{
if (num%i == 0){
a++;
}
}
if (a == 0){
return true;
}
return false;
}
//把数字nX分解成多个数字相乘，且每个数字的范围为0~9之间,不在这个范围则不合法
void getNumber(int nX, vector<int>&vcNumber){
if (nX<=0)
{
throw new std::exception("输入的数字必须为正整数！");
}
int nData = nX;
for (int i = 9; i > 0;i--)
{
if (nX<10)//输入的数小于10，压入1和本身
{
vcNumber.push_back(1);
vcNumber.push_back(nX);
break;//结束
}
if (nData<10)//压入本身
{
vcNumber.push_back(nData);
break;//结束
}
else if (isZhiShu(nData))//大于10且为质数
{
throw new std::exception("输入的数字为质数或者含有为质数的因子！");
}
else{
if (nData%i==0)//余数为0
{
vcNumber.push_back(i);
nData = nData/i;
i = 10;//回到起点
}
}
}
}
//降序排序比较函数
bool Comp(const int &a, const int &b)
{
return a > b;
}
int main(){
int nX;
vector<int> vcNumber;
while (true)
{
cout << "please input a number x:" << endl;
cin >> nX;
if (nX <= 0)
{
cout << "输入的数字必须为正整数，请重新输入！" << endl;
}
else{
getNumber(nX, vcNumber);
sort(vcNumber.begin(), vcNumber.end(),Comp);//降序排序
vector<int>::const_iterator iter;//逆序迭代器
int nOutput = 0;
int nCount = 1;
for (iter = vcNumber.begin(); iter != vcNumber.end(); ++iter)
{
nOutput += (*iter) * nCount;
nCount *= 10;
}
vcNumber.clear();
cout << "the minimum number y is:" << nOutput << endl;
}
}
return 0;
}
测试结果：
注意：这里对vector的排序使用STL中的sort函数，由于得到的vector里面的数字都是0~9范围，满足使用计数排序的条件，可以使用计数排序，时间复杂度为O(N)，关于计数排序，请看之前的博文：http://blog.csdn.net/liuyi1207164339/article/details/50830224