朱金灿                一个数的质因数分解式就是把一个数分为一个个质数因子，比如60，它的质因数分解式就是2 2 3 5 ，首先这几个数都是质数，其次它们相乘为60。看《算法设计与分析基础》，见到书上提到数的质因数分解式，便编了一个小程序实现求一个数的质因数分解式。算法思路是这样的： 1.       首先判断该数是否为质数，如果不是就进行分解，如果是就输出； 2.       分解步骤是这样的：使用循环从被分解数的平方根中开始相除，一旦相除余数为0，就分别对余数和商进行类似分解，退出循环。   很显然，这个算法要使用递归。   代码如下：   #include <iostream> using namespace std; #include <math.h> #include <conio.h>   // 判断一个数是否是素数 bool IsPrimeNum(int number) {     bool bIsPrimeNum = true;        for (int i = int(sqrt((double)number));i>1;i--)        {         if((number%i)==0)                bIsPrimeNum = false;        }        return bIsPrimeNum; }   // 分解 void DivideNum(int number) {     if(!IsPrimeNum(number))        {                for (int i = int(sqrt(number));i>1;i--)                {                       if((number%i)==0)                       {                           DivideNum(i); // 对除数进行分解                          number = number/i;                 DivideNum(number); // 对商进行分解                    break;                       }                                     }        }   else         cout<<number<<"   "; }     int main(int argc, char* argv[]) {        int number;     cout<<"please input a number: "<<endl;     cin>>number;        DivideNum(number);       cout<<endl;        getch();        return 0; }   运行效果如下图：

评论