Ubuntu16.04分解质因数（C++）

• • 网页工具
  • C++代码
  • 参考文章

网页工具

在线分解质因数计算器工具

C++代码

#include<string>
#include<iostream>
#include<sstream>


std::string stringify(int x)
 {
   std::ostringstream o;
   o << x  ;
   return o.str(); //返回临时对象
 }

//分解质因数   factor:将…分解成因子
std::string Factored(int i)
{
    std::string fac;
    fac = " = ";
    int p = 2;
    int temp = i;
    if (temp < 0 )
    {
        temp *= -1;
        fac += " -1 * ";
    }

    if ( 1 == temp) fac += " 1 ";
    if ( temp > 1)
    {
        int primefac = 0;
        while( temp > 1 && p * p <= temp)
        {
            if (temp % p == 0)
            {
                ++primefac;
                if (primefac > 1)
                {
                    fac += " * ";
                }

                fac += stringify( p) ;
                temp /= p;
                int exponent = 1; // 幂
                while (temp % p == 0)
                {
                    temp /= p;
                    ++exponent;
                } // while p is fac
                if ( exponent > 1)
                {
                    fac += "^" ;
                    fac += stringify( exponent) ;
                }
            }  // if p is factor

            ++p;
        } // while p

        if (temp > 1 && primefac >= 1) fac += " * ";
        if (temp > 1 ) fac += stringify( temp)  ;

    } // temp > 1

    return fac;
} // Factored

int main()
{
    std::cout<<Factored(45451512);
}

参考文章

如何用最简单的python方法求一个数的因子
Algorithms for Finding the Prime Factorization of an Integer