用埃拉托色尼筛算法求两个数最大公约数C++的实现

#include "stdafx.h"
#include "iostream"
#include <algorithm>
#include <vector>

//使用埃氏筛选法求最大公约数
void sort(int m, int n) ;

int main()
{
	int a, b;

	for (int i = 0; i < 3; )
	{
		std::cout << "请输入两个数" << "n";
		std::cin >> a >> b;

		std::cout << "n";

		sort(a, b);
		i++;
		if (i == 3)
		{
			std::cout << "是否继续,输入n退出或输入任意数继续n";
			char confirm;
			std::cin >> confirm;
			if (confirm != 'n')
				i = 0;
		}
	}
		system("pause");
    return 0;
}

void sort(int m, int n)
{
	int imax, imin;
	int sq;

	//取最大最小值
	imax = std::max(m, n);
	imin = std::min(m, n);

	//构造辅助数组
	bool *isTrue = new bool[imin];
	sq = sqrt(imin) + 1;

	//数组初始化
	for (int i = 2; i <= imin; i++)
	{
		isTrue[i] = true;

	}

	//数组中TRUE为质数
	for (int i = 2; i <= sq; i++)
	{
		if (isTrue[i])
		{
			for (int j = 2; j <= imin; j++)
			{
				if (j%i == 0 && i != j)
					isTrue[j] = false;
			}
		}
	}
	
	//打印质数
	for (int i = 2; i <= imin; i++)
	{
		if (isTrue[i])
			std::cout << "质数:" << i << std::endl;
	}
	std::cout << "nn";
	//求两数最大公约数
	int s = 1;//最大公约数
	for (int i = 2; i <= imin; )
	{
		//std::cout << i;
		if (isTrue[i])
		{
			if (imax%i == 0 && imin%i == 0)
			{
				imax /= i;
				imin /= i;
				s *= i;
				//std::cout <<imax<<imin<< i;
			}
			else ++i;
		}
		else ++i;
	}

	std::cout <<m<<"和"<<n<<"的最大公约数为" <<s << "n";
}