java - 在 JAVA 中计算一个数的相对素数？

Question

我正在开发一个程序，我在其中计算了一些类型 long根据我的算法应用一些计算后。现在，我必须找到我生成的这个数字的相对质数。我怎样才能做到这一点？我知道如果两个数是相对质数，那么它们的 GCD == 1但在这种情况下，我没有其他号码。我的程序中只有一个生成的数字，我需要为这个数字计算一个相对质数。

编辑

产生相对素数的条件是:

1 < relative prime < generated Number

感谢任何帮助。

Answer 1

获取相对质数的简单方法:

Now, I have to find a relative prime to this number

对于整数 n，其中 n>2 n 和 n-1 始终为真比较素。因此，假设 n 不是 2 或更小，只需将 n-1 作为输出即可，因为它保证相对质数。如果 n 等于 2，那么您的条件是不可能的。

非平凡的相对素数

如果您想要一个非平凡的解决方案，您始终可以实际计算 GCD。使用 Euclid 的方法如下:

long findGCD(long l1, long l2) {
    //end recursion
    if(l2 == 0){
        return number1;
    }
    return findGCD(l2, l1%l2);
}

并使用 while 循环尝试从 n+2 开始的所有数字，直到 GCD 为 1。