CODEWITHSUNDEEP
greatest-common-divisornumber-theory
Razib Hossain Shuvo
Razib Hossain Shuvo

Reputation: 39

How to find the GCD of some pairs of numbers of a given set?

I can calculate the GCD of two numbers. given a set S = {1,2,3,4,5} and i have to calculate the GCD of each pair like {1,2} = 1, {1,3} =1 , {1,4} = 1, {1,5} = 1, {2,3} = 1, {2,4} = 2, {2,5} = 1 and so on. I know the O(N^2) solution by just simply calculate the GCD of each pair which will give me TLE in case of big set for 2<=n<= 10^9 or more but i want to learn O(N*sqrt(N) ) solution or more better. i want the GCD of each pair separately.

Upvotes: 0

Views: 1832

Answers (2)

Tony Wu
Tony Wu

Reputation: 1107

You may write a program with Euclidean algorithm

Check out the example of finding GCD(1071,462)

GCD{1,2,3,4,5} = GCD{GCD{GCD{1,2},GCD{3,4}},5}

use Euclidean algorithm 4 times only to calclate the GCD of the given set S={1,2,3,4,5}

By using Euclidean, the only thing you need to do is finding the reminders until the number is disvisble.

Upvotes: 0

Naman
Naman

Reputation: 32028

Basic Euclidean Algorithm shall help.

int gcd(int a, int b){
    if (a == 0)
        return b;
    return gcd(b%a, a);
}

Interestingly if you want to find the GCD of entire set. All you need to do is form a subset from the obtained GCD and iterate unless only 1 final element is left. e.g S={1,2,3,4,5} => S1={GCD(1,2) , GCD(3,4) , add 5 } => S2={GCD(1,1) , and 5 } => S3={GCD(1,5)} => 1

Upvotes: 0

Related Questions