struct Number
{
	int num;
	int num2;
	int count;
	int* multipliers;
};

struct Number* initializeNumber(int a)
{
	struct Number* n = (struct Number*)malloc(sizeof(struct Number));
	n->num = a;
	n->num2 = a;
	n->count = 0;
	n->multipliers = NULL;
}

int viewNumber(struct Number* a)
{
	printf("num= %i\n", a->num);
	printf("num2= %i\n", a->num2);
	printf("divisors:");
	for (int i = 0; i < a->count; ++i)
	{
		printf("%i ", a->multipliers[i]);
	}
	printf("\n");
	return 0;
}

//assume a->num > 1
int factorization(struct Number* a)
{
	for (int i = 2; i<=a->num2; ++i) 
	{
		if (a->num2%i == 0)
		{
			a->count += 1;
			a->multipliers = (int*)realloc(a->multipliers, a->count*sizeof(int));
			a->multipliers[a->count - 1] = i;
			
			a->num2 /= i;
			factorization(a);
			break;
		}
	}
	return 0;
}

//Сочетания
char* la_combination(unsigned n, unsigned m)
{
	m = (n - m > m) ? m : n-m;
	int* up = (int*)malloc(sizeof(int)*m);//числитель
	int* down = (int*)malloc(sizeof(int)*m);//знаменатель

	for (int i = 1; i <= m; ++i)
	{
		*(up + m - i) = n - m + i;
		*(down + m - i) = i;
	}
#ifdef DEBUG
	for (int i = 0; i < m; ++i)
		printf("%i ", up[i]);
	printf("\n");
	for (int i = 0; i < m; ++i)
		printf("%i ", down[i]);
	printf("\n");
#endif

	int len_down = m;
	for (int i = 0; i < len_down; ++i)//1 проход по знаменателю, длина знаменателя меняется
	{
		if (down[i] != 1)
		{
			int j = 0;
			for (j = 0; j < m; ++j)//проход по числителю
			{
				if (!(up[j] % down[i]))
				{
					up[j] /= down[i];
					down[i] = 1;
					break;
				}
			}
			if (j == m && down[i]!=1) //если перебрали все элементы числителя, а фиксированный элемент знаменателя не сократили
			{
				struct Number* n = initializeNumber(down[i]);
				factorization(n); //раскладываю число на множители
				down[i] = 1;
				len_down += n->count;
				down = (int*)realloc(down, sizeof(int)*len_down);
				for (int i = 0; i < n->count; ++i)
				{
					down[len_down - n->count + i] = n->multipliers[i];
				}
				free(n->multipliers);
				free(n);
			}
		}
	}
#ifdef DEBUG
	for (int i = 0; i < m; ++i)
		printf("%i ", up[i]);
	printf("\n");
	for (int i = 0; i < len_down; ++i)
		printf("%i ", down[i]);
	printf("\n");
#endif
	char* res="1";
	char* t = (char*)malloc(10);
	for (int i = 0; i < m; ++i)
	{
		sprintf(t, "%d", up[i]);
		res = la_multiplication(res, t);
	}
	free(t);
	return res;
}