Number theory
closed account (379EvCM9)
How to divide an array of integers into two arrays having atleast one element each such that the GCD of array1 + GCD of array2 is maximum.
May be there is a better way, but I would put the two numbers with the best accordance in the set of prime factors in one array and all "show stoppers" to the second. Example:
8 and 12 have factor 2*2 in common, but 12 and 78 have 2*3 which is a bit better. So the first array is {12, 78} with GCD = 6 and the second {8, 125} with GCD = 1.
(BTW, those who need a brush up in fractions, get 125/12 - 78/8 with no help but pen and paper.)
8: 2*2*2 12: 2*2 *3 78: 2 *3 *13 125: 5*5*5 |
8 and 12 have factor 2*2 in common, but 12 and 78 have 2*3 which is a bit better. So the first array is {12, 78} with GCD = 6 and the second {8, 125} with GCD = 1.
(BTW, those who need a brush up in fractions, get 125/12 - 78/8 with no help but pen and paper.)
How to divide an array of integers -- where did this come from? Is it provided or picked to get the solution?
| two arrays having atleast one element each |
Question: How is the GCD of a single number defined?
The problem seems to be described much better in the other thread: http://www.cplusplus.com/forum/beginner/255076/#msg1118833
Topic archived. No new replies allowed.