<C++ 알고리즘> 두 수의 최대공약수 출력

반복횟수가 몇번인지 Pass By Reference로 해서 횟수를 검사했습니다.

 

// 최대 공약수 구하기 V1, V2, V3
#include <iostream>
#include <list>
using namespace std;

void CreateDivisorList(int Value, list<int>& divisorList, int& iter)
{
	for (int i = 1; i <= Value; ++i)
	{
		if (Value % i == 0)
		{
			divisorList.push_back(i);
			++iter;
		}
	}
}

int FindDivisor(list<int>& divisorA, list<int>& divisorB, int& iterRef)
{
	list<int>::reverse_iterator iter(divisorA.rbegin());
	list<int>::reverse_iterator iterEnd(divisorA.rend());

	for (; iter != iterEnd; ++iter)
	{
		list<int>::reverse_iterator iter1(divisorB.rbegin());
		list<int>::reverse_iterator iter1End(divisorB.rend());

		for (; iter1 != iter1End; ++iter1)
		{
			++iterRef;

			if ((*iter) == (*iter1))
			{
				return (*iter);
			}

		}
	}

	return INT_MAX;
}

int FindDivisor(int divisorA, list<int>& divisorBList, int& iterRef)
{
	list<int>::reverse_iterator iter(divisorBList.rbegin());
	list<int>::reverse_iterator iterEnd(divisorBList.rend());

	for (; iter != iterEnd; ++iter)
	{
		++iterRef;
		if (divisorA % (*iter) == 0)
		{
			return (*iter);
		}	
	}
	return INT_MAX;

}

int gcd_v1(int a, int b, int& iter)
{
	static list<int> divisorAList;
	static list<int> divisorBList;

	CreateDivisorList(a, divisorAList, iter);
	CreateDivisorList(b, divisorBList, iter);

	return FindDivisor(divisorAList, divisorBList, iter);
}


int gcd_v2(int a, int b, int& iter)
{
	static list<int> divisorAList;
	CreateDivisorList(a, divisorAList, iter);
	return FindDivisor(b, divisorAList, iter);
}

int gcd_v3(int a, int b, int& iter)
{
	int r = a % b;
	++iter;

	if (r != 0)
		gcd_v3(b, r, iter);

	return r;
}



int main()
{
	int iter = 0;
	int divisor = 0;

	divisor = gcd_v1(60, 28, iter);
	cout << "(" << iter << ", " << divisor << ")" << endl;

	iter = 0;
	divisor = 0;

	divisor = gcd_v2(60, 28, iter);
	cout << "(" << iter << ", " << divisor << ")" << endl;

	iter = 0;
	divisor = 0;

	divisor = gcd_v3(60, 28, iter);
	cout << "(" << iter << ", " << divisor << ")" << endl;

	return 0;
}