UsefullCode.net

与えられた数値を素因数分解する効率的な方法は見つかっていない。そのため素数もしくは素数と思われる数値で小さい方から順々に除算をして割り切れるかを確認するしかない。ここでは2と奇数に絞って割り切れるか調べることで素因数分解を実現した。

#include "math.h"
#include "atlcoll.h"
#include "atlstr.h"



class	CElementInfo
{
public:
	long	_nElement;
	ULONG	_nCount;

	CElementInfo()
	{
		_nElement = 0;
		_nCount = 0;
	}

	CElementInfo(long nElement,ULONG nCount)
	{
		_nElement = nElement;
		_nCount = nCount;
	}

	CElementInfo&	operator++()
	{
		_nCount++;
		return	*this;
	}
	CElementInfo&	operator++(int)
	{
		_nCount++;
		return	*this;
	}

	CElementInfo&	operator--()
	{
		if(_nCount)
			_nCount--;
		return	*this;
	}
	CElementInfo&	operator--(int)
	{
		if(_nCount)
			_nCount--;
		return	*this;
	}
};



//
//	素因数分解
//
bool	Digest(long nData,CAtlArray<CElementInfo>* pacElements)
{
	long	nElement;
	ULONG	nCount;
	long	nLoopMax;

	if(pacElements == NULL)
		return	false;
	pacElements->RemoveAll();

	//負の数なら素因数として-1を与える
	if(nData < 0)
	{
		pacElements->Add(CElementInfo(-1,1));
		nData *= -1;
	}
	if(nData == 0 || nData == 1)
		return	true;

	nLoopMax = (long)sqrt((double)nData) + 1;
	for(nElement = 2; nElement <= nLoopMax; nElement += 2)
	{
		if(nElement == 4)	//2で素因数分解を１回行った後は3,5,7...2n+1で処理を
			nElement--;	//行なうように4のときに1を減算

		nCount = 0;
		while(1)
		{
			if(nData % nElement)
				break;

			nCount++;
			nData /= nElement;
		}
		if(nCount > 0)
			pacElements->Add(CElementInfo(nElement,nCount));
		if(nData == 1)
			break;
	}
	if(nData > 1)
		pacElements->Add(CElementInfo(nData,1));

	return	true;
}




bool	Test()
{
	size_t	i;
	size_t	nSize;
	ULONG	j;
	long	n;
	CAtlString	strMessage;
	CAtlString	strBuff;
	CAtlArray<CElementInfo>	acElements;


	////////////////////////
	//素因数分解実行
	//
	n = 234;
	Digest(n,&acElements);


	////////////////////////
	//結果表示
	//
	strBuff.Format(_T("%d ＝ "),n);
	strMessage += strBuff;

	nSize = acElements.GetCount();
	for(i = 0; i < nSize; i++)
	{
		if(i > 0)
			strMessage += _T("×");

		strBuff.Format(_T("%d"),acElements[i]._nElement);
		strMessage += strBuff;

		for(j = 0; j < acElements[i]._nCount -1; j++)
		{
			strBuff.Format(_T("×%d"),acElements[i]._nElement);
			strMessage += strBuff;
		}
	}

	::MessageBox(NULL,strMessage,_T("結果"),MB_OK);

	return	true;
}

プロジェクトファイルをダウンロード