#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

struct numExp //структура числа представленного в виде массива множетилей
{
    int keyArray;       //текущий индекс массива
    int val;            //число из которого получился ряд простых множетилей
    int keys;           //максимально вохможный индекс массива множетилей
    int number[64];     //массив множетилей
    int exponent[64];   //массив показателей степеня, индекс массив числа соответствует индексу массива степеней
};



int getNextSimpNum(int val)//рекурсивная функция для нахождения простых чисел,  в качестве аргумента принимает число после которого нужно найти простое число
{                          //например приняли 3 вернули 5, приняли 5 вернули 7 и так далее
    val++;
    while(1)
    {
        for(int i = 2; i < val; i++)
        {
            if(val%i == 0)
            {
                val = getNextSimpNum(val);
                break;
            }
            if(i == val - 1)
            {
                return val;
            }
        }
    }
}
int getDividers(int val, int *temp)//функция для нахождения множетилей числа, в качестве аргумента принимает число которое нужно разложить на простые множители
{                                  //и принимает адресс массива в котором эти множители нужно разместить.  возвращает количество множетилей
    if(val < 2)
    {
        return 0;
    }

    int val2 = val;
    int divide = 2;
    int exp;
    int keyCount = -1;
    //int temp[1024][2];

    while(val > 1) //раскладываем число на простые множители
    {

        exp = 0;
        while(!(val % divide)) //пока число делится на делитель
        {
            val /= divide;
            exp++;
        }
        if(exp > 0 && keyCount < 62)
        {
            keyCount++;
            *temp = divide;
            temp++;
            *temp = exp;
            temp++;
        }
        divide = getNextSimpNum(divide);

    }
    if(keyCount == -1)
    {
        keyCount++;
        *temp = val2;
        temp++;
        *temp = 1;
        temp++;
    }
    return keyCount;
}
void clearArray(int *temp)//очистка массива
{
    for(int i = 0; i < 64; i++)
    {
        *temp = -1;
        temp++;
        *temp = -1;
        temp++;
    }
}


int main()
{
    setlocale(LC_ALL, "Russian");
    int numb[64][2];
    clearArray(&numb[0][0]);
    int key;
    int c, x, z, minNum, buffer;
    bool trig, trig2;
    trig = trig2 = true;
    numExp numberExpon[10];
    buffer = 1;
    cout << "Введите число ";
    cin >> c;
    for(x = 0; x < 10 && c > 1; x++ )
    {
        if( (key = getDividers(c, &numb[0][0])) >= 0 )
        {
            numberExpon[x].keyArray = 0;
            numberExpon[x].val = c;
            numberExpon[x].keys = key;
            for(int i = 0; i <= key; i++)
            {
                numberExpon[x].number[i] = numb[i][0];
                numberExpon[x].exponent[i] = numb[i][1];
            }
        }
        cout << "Введите -1 для завершения или следующие число для продожения ";
        cin >> c;
    }
    cout << "Для чисел: ";
    for(int y = 0; y < x; y++)
    {
        cout  << numberExpon[y].val << "   ";
    }
    cout << endl << "наибольший общий делитель будет равен: ";
    /*
    Алгоритм работает по следующему принципу
    Есть число которое разбито на массив простых чисел которые являются множетилями данного числа
    Такие множетили сформированны в структуры(далее по программе группы)
    в каждой структуре определенны поля, основные поля это массив чисел и массив степеней
    принцип следующий в каждой структуре массив чисел идет упорядоченого от меньшего числа к большему
    то есть например есть числа 6 и 9, изобразим ряд множителей 2, 3 и ряд множителей 3 квадрат
    первая структура содержит массив чисел 2, 3 а вторая массив чисел 3 и массив степеней указывает что это квадрат
    сравним первый елемент массива в структуре числа 6 и в (далее по тексту соседней) структуре числа 9
    в (далее по тексту текущей)структуре числа 6 первым елементом будет число 2 которое меньше
    чем первый елемент числа в соседней структуре тогда мы в текущей структуре переходим на следующий елемент массива и повторяем
    сравнение числа в текущей структуре и соседней равны, если структур больше 2-х тогда соседняя становится текущей и следующая
    за текущей становится соседней, повторяются те же сравнения и так до тех пор пока не будут найдены все елементы одинаковые елементы структур
    после чего находится наименьший показатель степени данных чисел и производится расчет степени числа результат которого умножается на буферную переменую
    затем если не достигнут был верхняя граница массива то есть еще есть числа которые могут быть одинаковы во всех структурах то поднимаемся на
    следующий индекс первой структуры и производим сравнения, после чего так же множим результат возведения в степень на буферную переменную
    когда же все числа будут найдены выводим результат
    */
    while(trig2 && trig) // до тех пор пока не отобранны все группы либо пока не пришли к границе массива множителей одной из групп
    {
        for(int i = 0; i<x-1; i++)//перебираем группы множетелей
        {
            for(; numberExpon[i].keyArray <= numberExpon[i].keys;)
            {
                if(numberExpon[i].number[numberExpon[i].keyArray] > numberExpon[i+1].number[numberExpon[i+1].keyArray])//если елемент нашей группы множителей больше соседнего то переключаем следующий елемент у соседней группы
                {
                    if(numberExpon[i+1].keyArray == numberExpon[i+1].keys)//если мы подошли к границам массива
                    {
                        i=x; // счетчик цикла становится равным границе цикла для выходя из него
                        trig = false;
                        break;
                    }
                    numberExpon[i+1].keyArray++;//увеличиваем индивидуальный ключ массива соседней группы множетилей

                }
                else if(numberExpon[i].number[numberExpon[i].keyArray] < numberExpon[i+1].number[numberExpon[i+1].keyArray])//если елемент нашей группы множителей меньше соседнего то переключаем следующий елемент у нашей группы
                {
                    if(numberExpon[i].keyArray == numberExpon[i].keys)
                    {
                        i=x; // счетчик цикла становится равным границе цикла для выходя из него
                        trig = false;
                        break;
                    }
                    if(i == 0)//если первое вхождение в цикле перебора групп множетилей
                    {
                        numberExpon[i].keyArray++;//увеличиваем индивидуальный ключ массива текущей группы множетилей
                    }
                    else
                    {

                        numberExpon[i].keyArray++;//увеличиваем индивидуальный ключ массива текущей группы множетилей
                        i = 0; //сбрасываем счетчик цикла перебора групп множетилей для повторной перегрупировки
                    }


                }
                else
                { //если множитель текущей группы равен соседнему то пропускаем итерацию цикла для перехода к сравнению следующих групп
                    break;
                }
            }
        }
        if(trig)//если мы не дошли до границы массива какой либо из групп множетилей
        {
            minNum = numberExpon[0].exponent[numberExpon[0].keyArray];
            for(int i = 0; i < x; i++)//ищем самый малый показатель степени множетилей
            {
                if(minNum > numberExpon[i].exponent[numberExpon[i].keyArray])
                {
                    minNum = numberExpon[i].exponent[numberExpon[i].keyArray];
                }
            }
            buffer *=  (int)(pow(numberExpon[0].number[numberExpon[0].keyArray], minNum)+0.5); //умножаем значение буффера на резудьта возведения в степень множетиля
        }
        if(numberExpon[0].keyArray < numberExpon[0].keys)// если массив чисел самой первой группы множетилей не достиг своей границы то переходим на следующую ячейку
        {
            numberExpon[0].keyArray++;
        }
        else //если достигли границ массива обрывам цикл
        {
            trig2 = false;
        }
    }
    if(buffer > 1)
    {

        cout << buffer <<endl;
    }
    else
    {

        cout << buffer << " числа взаимно простые" << endl;
    }
}