Java 判断两个整数互质

判断两个整数是否互质可以使用欧几里得算法（又称辗转相除法）。如果两个数的最大公约数是 1，则这两个数互质。

以下是 Java 代码实现：

public static boolean isCoprime(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a == 1;
}

使用示例：

int a = 6;
int b = 35;
if (isCoprime(a, b)) {
    System.out.println(a + " 和 " + b + " 互质");
} else {
    System.out.println(a + " 和 " + b + " 不互质");
}

输出结果：

6 和 35 互质

相关问题

java判断是否是斐波那契数

在Java中判断一个数是否是斐波那契数，可以通过数学方法来实现。斐波那契数列是一个递归数列，其定义为：
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2), 对于 n > 1

斐波那契数列中的一些基本性质包括：
1. 一个数是斐波那契数当且仅当5乘以它的平方加4或者是完全平方数。
2. 一个数是斐波那契数当且仅当它的两个相邻数是互质的（即它们的最大公约数是1）。

根据这些性质，我们可以编写一个方法来判断一个数是否为斐波那契数。这里提供一个基于数学性质1的判断方法：

public class FibonacciChecker {

    public static boolean isFibonacci(int number) {
        // 一个数是斐波那契数当且仅当5乘以它的平方加4是完全平方数
        int temp = (5 * number * number + 4);
        int sqrtValue = (int) Math.sqrt(temp);
        
        // 检查平方根是否是整数
        return sqrtValue * sqrtValue == temp;
    }

    public static void main(String[] args) {
        int numberToCheck = 21;
        if (isFibonacci(numberToCheck)) {
            System.out.println(numberToCheck + " 是斐波那契数");
        } else {
            System.out.println(numberToCheck + " 不是斐波那契数");
        }
    }
}

这段代码定义了一个`isFibonacci`方法，它接受一个整数参数，返回一个布尔值表示该数是否为斐波那契数。在主方法`main`中，我们调用该方法并打印结果。

不借助现有API，使用java编程欧几里得扩展算法，利用实现求整数乘法逆元

好的，我可以帮您解答这个问题。

在数学中，如果两个整数a和m是互质的，那么a对于模m的逆元存在。具体来说，对于给定的整数a和m，求一个整数x，使得ax ≡ 1(mod m)成立，那么x就是a对于模m的逆元。

欧几里得扩展算法可以用来求整数乘法逆元。具体来说，我们可以使用以下的Java代码实现：

public static int extendedEuclidean(int a, int b) {
    int m = a, x = 1, y = 0;
    int n = b, u = 0, v = 1;
    while (n != 0) {
        int q = m / n;
        int r = m % n;
        int s = x - u * q;
        int t = y - v * q;
        m = n;
        n = r;
        x = u;
        y = v;
        u = s;
        v = t;
    }
    int gcd = m;
    int inv = x;
    if (gcd != 1) {
        // a与m不互质，不存在乘法逆元
        inv = -1;
    } else {
        // 将乘法逆元转换为正整数
        inv = (inv % b + b) % b;
    }
    return inv;
}

其中，a和m是要求的整数，返回值为a在模m下的乘法逆元。

该算法的时间复杂度为O(log(m))，在实际应用中具有较高的效率和可用性。