#include <stdio.h>
#define SIZE 5
int lcm(int, int);
int gcd(int, int);
void swap(int&, int&);
void search(int *vals, int index, int lcm);
int main()
{
int vals[SIZE];
for(int n=2; n<SIZE; n++)
{
vals[0]=n;
search(vals, 1, n);
}
}
// currentLCM is the LCM of all values in the array before index
void search(int *vals, int index, int currentLCM)
{
// Compute currentLCM/vals[0] + currentLCM/[1] + ...
int sum = 0;
for(int i=0; i<index; i++)
sum += currentLCM/vals[i];
if(currentLCM<=sum) return; // current sum is too big
if(index==SIZE-1)
{
int rem = currentLCM - sum;
if(currentLCM%rem == 0)
{
vals[SIZE-1] = currentLCM/rem;
if(vals[SIZE-1] > vals[SIZE-2]) // don't allow a duplicate on the last value
{
for(int i=0; i<SIZE; i++)
printf("%d ", vals[i]);
printf("\n");
}
}
}
else
{
int minNext = vals[index-1] + 1;
int valsLeft = SIZE - index;
int maxNext = currentLCM * valsLeft / (currentLCM - sum);
for(int i=minNext; i<=maxNext; i++)
{
vals[index] = i;
search(vals, index+1, lcm(i, currentLCM));
}
}
}
// Finds lowest common multiple of two integers
int lcm(int x, int y)
{
return x/gcd(x,y)*y;
}
// Finds gcd of two integers
int gcd(int x, int y)
{
if(x<y) swap(x,y);
if(y==0) return x;
return gcd(x%y, y);
}
// Swap two integers sexily
void swap(int &x, int &y)
{
x=x^y;
y=x^y;
x=x^y;
}