java - javaで上限数10000のgcdペアを見つける効率的な方法

Question

GCD=1 から特定の数 (たとえば 10000) までのペアを見つけたいと考えています。2 つのネストされたループを使用し、長いパラメータを持つメソッドを呼び出しています。しかし、コードの実行速度は非常に遅いため、効率的なアプローチが必要です。ありがとう

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);
        }
    }
}