求一个数的质因数分解式

 一个数的质因数分解式就是把一个数分为一个个质数因子，比如60，它的质因数分解式就是2 2 3 5 ，首先这几个数都是质数，其次它们相乘为60。看《算法设计与分析基础》，见到书上提到数的质因数分解式，便编了一个小程序实现求一个数的质因数分解式。算法思路是这样的：

1.       首先判断该数是否为质数，如果不是就进行分解，如果是就输出；

2.       分解步骤是这样的：使用循环从被分解数的平方根中开始相除，一旦相除余数为0，就分别对余数和商进行类似分解，退出循环。

 

很显然，这个算法要使用递归。

 

代码如下：

 

#include

using namespace std;

#include

#include

 

// 判断一个数是否是素数

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<

}

 

 

int main(int argc, char* argv[])

{

       int number;

    cout<<"please input a number: "<

    cin>>number;

       DivideNum(number);

      cout<

       getch();

       return 0;

}