1

我想找到 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);
        }
    }
}
4

2 回答 2

2

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

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

其中之一是欧几里得算法

虽然存在更多

生成共素数（您似乎想要的）

这应该有帮助

于 2013-09-27T15:04:32.733 回答
0

生成所有互质对

所有互质数对 m, n 可以排列在一对不相交的完全三叉树中，从 (2,1) 开始（对于奇偶对或奇偶对）或从 (3,1) 开始（对于奇奇对）。

每个顶点 (m,n) 的子节点生成如下：

分支 1: (2m-n,m)

分支 2: (2m+n,m)

分支 3: (m+2n,n)

该方案是详尽无遗的，没有无效成员。

来自维基百科

这两个三叉树可以很容易地在 Java 中构建（一个以 (2,1) 开头，另一个以 (3,1) 开头）。您可以将上限放在生成函数中。

这将比你的蛮力方法更有效。

于 2013-09-27T15:37:38.810 回答