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;
}





//
//	平方根
//
//pacInnerElementsはルートの中側
//pacOuterElementsはルートの外側
//
bool	SquareRoot(long nData,CAtlArray<CElementInfo>* pacInnerElements,CAtlArray<CElementInfo>* pacOuterElements)
{
	bool	ret;
	CAtlArray<CElementInfo>	acDigest;

	if(pacInnerElements)
		pacInnerElements->RemoveAll();
	if(pacOuterElements)
		pacOuterElements->RemoveAll();
	if(pacInnerElements == NULL || pacOuterElements == NULL)
		return	false;

	if(nData == 0 || nData == 1 || nData == -1)
		return	true;

	//素因数分解
	ret = Digest(nData,&acDigest);
	if(ret == false)
		return	false;

	size_t	i;
	size_t	nSize;

	nSize = acDigest.GetCount();
	for(i = 0; i < nSize; i++)
	{
		if(acDigest[i]._nCount == 1)
			pacInnerElements->Add(CElementInfo(acDigest[i]._nElement,1));
		else if(acDigest[i]._nCount % 2 == 0)
			pacOuterElements->Add(CElementInfo(acDigest[i]._nElement,acDigest[i]._nCount / 2));
		else
		{
			if(acDigest[i]._nCount != 0)
			{
				pacInnerElements->Add(CElementInfo(acDigest[i]._nElement,1));
				pacOuterElements->Add(CElementInfo(acDigest[i]._nElement,acDigest[i]._nCount / 2));
			}
		}
	}

	return	true;
}



//
//	平方根
//
//pacInnerElementsはルートの中側
//pacOuterElementsはルートの外側
//
bool	SquareRoot(long nData,long* pnInner,long* pnOuter)
{
	bool	ret;
	CAtlArray<CElementInfo>	acInnerElements;
	CAtlArray<CElementInfo>	acOuterElements;

	if(pnInner)
		*pnInner = 0;
	if(pnOuter)
		*pnOuter = 0;
	if(pnInner == NULL || pnOuter == NULL)
		return	false;
	if(nData == 0)
		return	true;


	////////////////////////////////////
	//平方根の計算
	//
	ret = SquareRoot(nData,&acInnerElements,&acOuterElements);
	if(ret == false)
		return	false;


	////////////////////////////////////
	//結果値の計算
	//

	size_t	i;
	size_t	j;
	size_t	nSizeI;
	size_t	nSizeJ;

	*pnInner = 1;
	nSizeI = acInnerElements.GetCount();
	for(i = 0; i < nSizeI; i++)
	{
		nSizeJ = acInnerElements[i]._nCount;
		for(j = 0; j < nSizeJ; j++)
			*pnInner *= acInnerElements[i]._nElement;
	}

	*pnOuter = 1;
	nSizeI = acOuterElements.GetCount();
	for(i = 0; i < nSizeI; i++)
	{
		nSizeJ = acOuterElements[i]._nCount;
		for(j = 0; j < nSizeJ; j++)
			*pnOuter *= acOuterElements[i]._nElement;
	}

	return	true;
}






bool	Test()
{
	bool	ret;
	long	nData;
	long	nInner;
	long	nOuter;
	CAtlString	strBuff;
	CAtlString	strMessage;

	nData = 200;

	ret = SquareRoot(nData,&nInner,&nOuter);
	if(ret == false)
		return	false;

	strMessage.Format(_T("√%d ＝ %d√%d"),nData,nOuter,nInner < 0 ? nInner*-1 : nInner);
	if(nInner < 0)
		strMessage += _T("i");

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

	return	true;
}

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