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

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

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

显然,此方法仅将返回truefalse,因为main函数仅将打印特定的行,具体取决于这两个数字是否是相对质数。

我在想我可能必须编写两个for循环,分别用于input4input5,还可能需要编写带有逻辑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/

10-11 22:21
查看更多