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

Answer 1

其中许多问题已经得到解决。

检查维基百科或其他来源的算法。

其中之一是 the Euclidean algorithm

尽管存在更多

生成余素数(您似乎想要)

This Should help