Author mrabarnett
Recipients akira, brg@gladman.plus.com, gladman, mark.dickinson, mrabarnett, scoder, steven.daprano, terry.reedy, vstinner, wolma
Date 2014-09-25.14:55:14
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1411656914.34.0.446760792219.issue22477@psf.upfronthosting.co.za>
In-reply-to
Content
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.
History
Date User Action Args
2014-09-25 14:55:14mrabarnettsetrecipients: + mrabarnett, terry.reedy, mark.dickinson, scoder, vstinner, steven.daprano, akira, wolma, gladman, brg@gladman.plus.com
2014-09-25 14:55:14mrabarnettsetmessageid: <1411656914.34.0.446760792219.issue22477@psf.upfronthosting.co.za>
2014-09-25 14:55:14mrabarnettlinkissue22477 messages
2014-09-25 14:55:14mrabarnettcreate