CODEWITHSUNDEEP
java
sudhir
sudhir

Reputation: 147

efficient way to find gcd pairs for an upper bound number, 10000 in java

I want to find pairs having GCD=1 upto a certain number, say 10000. I am using 2 nested loops and calling a method with long parameters. but code is running damn slow, any efficient approach is required. Thanks

class FastGCD {

    public static long GCD(long a, long b) {

        return (b == 0 ? a : GCD(b, a % b));
    }

    public static void main(String ah[]) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cases = 0;

        long number = 0, output = 0;
        try {
            cases = Integer.parseInt(br.readLine());

        } catch (NumberFormatException e) {
            System.exit(0);
        } catch (IOException e) {
            System.exit(0);
        }
        for (int i = 1; i <= cases; i++) {
            try {
                number = Long.parseLong(br.readLine());
                } catch (NumberFormatException e) {
                e.printStackTrace();
                System.exit(0);
            } catch (IOException e) {
                e.printStackTrace();
                System.exit(0);
            }
            for (int j = 0; j < number; j++) {
                for (int k = 0; k < number; k++) {

                    if (FastGCD.GCD(j, k) == 1)
                        {
                        //System.out.println("here"+j+","+k);
                        output++;
                    }
                }
            }
            System.out.println(output);
        }
    }
}

Upvotes: 1

Views: 929

Answers (2)

zakinster
zakinster

Reputation: 10698

Generating all coprime pairs

All pairs of coprime numbers m, n can be arranged in a pair of disjoint complete ternary trees, starting from (2,1) (for even-odd or odd-even pairs) or from (3,1) (for odd-odd pairs).

The children of each vertex (m,n) are generated as follows:

Branch 1: (2m-n,m)

Branch 2: (2m+n,m)

Branch 3: (m+2n,n)

This scheme is exhaustive and non-redundant with no invalid members.

from Wikipedia

These two ternary trees can easily be build in Java (one starting with (2,1), the other one starting with (3,1)). You can put your upper bound inside the generation function.

It will be much more efficient than your brute-force approach.

Upvotes: 0

exussum
exussum

Reputation: 18558

Many of these problems are already solved.

Check wikipedia or other sources for algorithms.

One of this is the Euclidean algorithm

though more exist

To generate the co prime numbers (Which you seem to want)

This Should help

Upvotes: 2

Related Questions