分解质因数

/*
* Copyright (c) 2004
* All rights reserved.
*
* 文件名称： PrimeFactor.cpp
* 文件标识： 见配置管理计划书
* 摘        要： 把一个数分解成质因数相乘的形式
*
* 当前版本： 1.0
* 作        者： 田东
* 完成日期： 2004年12月5日
*
* 取代版本： 1.0
* 原 作 者： 输入原作者（或修改者）名字
* 完成日期： 2004年12月5日
*/
#include <iostream>
#include <math.h>

using namespace std;

void print(long p, int i);

int main(void)
{
    char *s;
    int i;
    long n, x, p;

    for(;;)
    {
     cout<<endl<<"input the number to be decompound('0' to quit):"<<endl;
     cin>>n;
     
        if(n < 2)break;
       
        print(n, 0);
       
        for(p=2, i=0; (n % p) == 0; i++)
        {
            n /= p;
        }
       
        if(i > 0)
        {
            print(p, i);
        }
       
        if( n == 1)
        {
            continue;
        }
       
        x = (long)sqrt((float)n);
        for(p=3; p <= x; p +=2)
        {
            for(i=0; (n % p) == 0; i++)
            {
                n /= p;
            }
           
            if(i > 0)
            {
                print(p, i);
            }
           
            x = (long)sqrt((float)n);
        }
       
        if(n > 1)
        {
            print(n, 1);
        }
    }
   
    system("pause");
   
    return 0;
}

void print(long p, int i)
{
    if(i == 0)
    {
        cout<<"> "<<p<<" = 1";
    }
    else
    {
        cout<<" * "<<p;
        if(i > 1)
        {
            cout<<"^"<<i;
        }
    }
}

本文地址：http://com.8s8s.com/it/it24663.htm