gladman added the comment: On 25/09/2014 15:55, Matthew Barnett wrote: > > Matthew Barnett added the comment: > > After some thought, I've come to the conclusion that the GCD of two integers > should be negative only if both of those integers are negative. The basic > algorithm is that you find all of the prime factors of the integers and then > return the product of the common subset (multiset, actually). > > For example, to calculate the GCD of 6 and 15: > > 6 => [2, 3] > 15 => [3, 5] > The largest common subset is [3]. > Therefore the GCD is 3. > > What about negative integers? > > Well, what you could do is make one of the factors -1. > > For example, to calculate the GCD of -6 and 15: > > -6 => [-1, 2, 3] > 15 => [3, 5] > The largest common subset is [3]. > Therefore the GCD is 3. > > Another example, to calculate the GCD of -6 and -15: > > -6 => [-1, 2, 3] > -15 => [-1, 3, 5] > The largest common subset is [-1, 3]. > Therefore the GCD is -3.
But should the computation of the GCD of two integers by finding the intersection of their prime factors include -1 or 1 given that neither of these is a prime? :-) ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue22477> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
