UsefullCode.net


Visual Studio 2005/2008/2010やandroid SDK/NDKでの開発者向けに便利なソースコードを提供
This site provide you with useful source codes under 'USEFULLCODE license'.

数値を素因数分解する

2007年02月11日 16:47
0件のコメント

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

依存環境:ATL
#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で素因数分解を1回行った後は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;
}

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


タスクトレイ常駐プログラムを簡単に作る
分数を約分する
トップページに戻る
issei.