如何找出两个数字是否是质数？

Question

我正在尝试编写一种方法，该方法将计算两个数字是否是赋值的相对质数。我主要是在寻找从哪里开始的答案。我知道有一种方法gcd()可以为我做很多事情，但是赋值几乎使我无需使用gcd或数组就可以做到。

我有点开始了，因为我知道我将不得不%在for循环中使用运算符。

public static boolean relativeNumber(int input4, int input5){
    for(int i = 1; i <= input4; i++)

显然，此方法仅将返回，true或者false因为该main函数仅将根据这两个数字是否相对质数来打印特定行。

我想我可能不得不写两个for循环，无论是input4和input5，可能还有一些类型的if语句逻辑&&操作数，但我不知道。

Answer 1

好在万一它们是相对质数的情况下，最大的公共除数是一个，因为-否则，两个数字都可以由该数字划分。因此，我们只需要一种算法来计算最大的公共除数，例如
Euclid的方法
：

private static int gcd(int a, int b) {
    int t;
    while(b != 0){
        t = a;
        a = b;
        b = t%b;
    }
    return a;
}

然后：

private static boolean relativelyPrime(int a, int b) {
    return gcd(a,b) == 1;
}

Euclid算法 在 O（log n）中工作 ，因此比枚举可以优化为 O（sqrt n）的 所有潜在除数要快得多。