1164 eddy's research i.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1164 Eddy's research I
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 5120 K

46 MS 432 KB 1694 B
GUN C++
*/
//求素数因子
#include <iostream.h>
using namespace std;

const int Max=65535;
const int pMax=6600;
int prime[pMax]={0},pnow=0;
int multiply[100]={0},mnow;

int divFind(int num)
{
    int low=0,high=pnow,mid;
    while(high-low>=0)
    {
        mid=(low+high)/2;
        if(prime[mid]==num)
            return mid;
        else
        {
            if(prime[mid]>num)
            {   high=mid-1;}
            else
            {   low=mid+1;}
        }
    }
    return -1;
}

int findPrime()
{
    bool num[Max]={false};
    int ca,temp;
    for(ca=2;ca<=Max;ca++)
    {
        if(num[ca-2]==false)
        {
            prime[pnow]=ca;
            pnow++;
            temp=ca+ca;
            while(temp<=Max)
            {
                num[temp-2]=true;
                temp+=ca;
            }
        }
    }//for
    pnow--;
    return 0;
}

int dfs(int x,int step)
{
    int ca,temp;
    if(divFind(x)>0)
    {   multiply[mnow]=x;mnow++;return 1;}
    for(ca=0;ca<=pnow;ca++)
    {
        if(x%prime[ca]==0)
        {
            multiply[mnow]=prime[ca];mnow++;
            temp=x/prime[ca];
            return dfs(temp,step+1);

        }
    }
    return 0;
}

int main()
{
    int x,n,ca;
    
    findPrime();
    
    while(cin>>x)
    {
        mnow=0;
        dfs(x,1);
        for(ca=0;ca<mnow;ca++)
        {
            cout<<multiply[ca];
            if(ca<mnow-1)
                cout<<"*";
            else
                cout<<endl;
        }
    }

    return 0;
}