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

我正在尝试编写一种方法，该方法将计算两个数字是否是赋值的相对质数。我主要是在寻找从哪里开始的答案。我知道有一种方法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操作数的某种&&语句，但是我不确定。

最佳答案

好吧，如果它们是相对质数，则最大的公共(public)除数是1，因为-否则-两个数字都可以由该数字划分。因此，我们只需要一种算法来计算最大的公共(public)除法器，例如Euclid's method:

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)的潜在除数快得多。

关于java - 如何找出两个数字是否是质数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28575416/