factor.cpp

整数因子分解问题 大于1 的正整数n可以分解为：n=x1*x2*…*xm。对于给定的正整数n

#include<iostream.h>
#include<fstream.h>
#include<math.h>
class Factor
{
public:
	Factor()
	{
		theStoreList=0;
	}
	~Factor()
	{
		if(theStoreList!=0)
		{
	
		delete[] theStoreList;
		theStoreList=0;
		}

	}
    int DoFactor(int p_Value)
	{
		if(p_Value<=1)
			return 0; 
		int t_Total=0;
		for(int t_Index=2;t_Index<=p_Value-1;t_Index++)
		{
			if(p_Value%t_Index==0)
				t_Total+=DoFactor(p_Value/t_Index);
		}
		return t_Total+1;
	}
	int DoQuickFactor(int p_Value)
	{
		if(p_Value<=1)
			return 0;
		InitializeList(p_Value);
		return QuickFactor(p_Value);
		
			
	}
private:
	int theFactorNum;
	int *theStoreList;
	int theLenth;
	
	void InitializeList(int p_Value)
	{
		theLenth=(int)sqrt(p_Value);
		theStoreList=new int[theLenth+1];
		for(int t_Index=0;t_Index<=theLenth;t_Index++)
			theStoreList[t_Index]=0;
	}
	int QuickFactor(int p_Value)//把p_Value分成a*b的形式；
	{
		if(p_Value<=theLenth&&theStoreList[p_Value]>0)
			return theStoreList[p_Value];
		int t_FactorNum=1;
		int t_Size=(int)sqrt(p_Value);
		for(int t_Index=2;t_Index<=t_Size;t_Index++)
		{
			if(p_Value%t_Index==0)
			{
				t_FactorNum+=QuickFactor(t_Index);//a<=sqrt(p_Value);
				t_FactorNum+=QuickFactor(p_Value/t_Index);//a>sqrt(p_Value);
			}
		}
		if(t_Size*t_Size==p_Value)//若存在a=b;则减去一个；
			t_FactorNum-=QuickFactor(t_Size);
		if(p_Value<=theLenth&&theStoreList[p_Value]<=0)
			theStoreList[p_Value]=t_FactorNum;


		//cout<<"total factor is  "<<theFactorNum<<endl;
		return t_FactorNum;
	}
	
};

void main()
{
	int len=0;
	fstream fs,os;
	fs.open("input.txt",ios::in);
	fs>>len;
	fs.close();
	os.open("output.txt",ios::out);
	Factor a;
	os<<a.DoQuickFactor(len);
	//os<<a.DoFactor(len);
	os.close();
	//cout<<"finish"<<endl;
	
}