Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement