如何判断两个数是否互质？

Question

我正在尝试编写一种方法来计算两个数字是否互素以进行赋值。我主要是在寻找从哪里开始的答案。我知道有一种方法 gcd() 可以为我完成很多工作，但作业几乎让我在没有 gcd 或数组的情况下完成它。

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

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

显然这个方法只用于 return true 或 false 因为 main 函数只会根据两个数字是否打印特定的行是不是相质数

我想我可能必须写两个 for 循环，都用于 input4 和 input5，并且可能需要某种 if 语句一个合乎逻辑的 && 操作数，但我不确定。

Answer 1

package stack;

import java.util.Scanner; //To read data from console

/**
*
* @author base
*/
public class Stack {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); // with Scanner we can read data
        int a = in.nextInt(); //first variable
        int b = in.nextInt(); //second variable
        int max; // to store maximum value from a or b
        //Let's find maximum value
        if (a >= b) {
            max = a;
        } else {
            max = b;
        }
        int count = 0; // We count divisible number
        for (int i=2; i<=max; i++) { // we start from 2, because we can't divide on 0, and every number divisible on 1
            if (a % i == 0 && b % i==0) {
                count++; //count them
            }
        }
        if (count == 0) { // if there is no divisible numbers
            System.out.println("Prime"); // that's our solutions
        } else {
            System.out.println("Not Prime"); //otherwise
        }
    }
}

我认为这是简单的解决方案。在评论中提问。

Answer 2

好吧，如果它们互质，最大公除数是 1，因为 - 如果不是这样 - 两个数都可以被那个数除。所以我们只需要一个算法来计算最大公约数，比如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).

Answer 3

Swift 4 @williem-van-onsem 答案的代码；

func gcd(a: Int, b: Int) -> Int {
    var b = b
    var a = a
    var t: Int!

    while(b != 0){
        t = a;
        a = b;
        b = t%b;
    }
    return a
}

func relativelyPrime(a : Int, b: Int) -> Bool{
    return gcd(a: a, b: b) == 1
}

用法；

print(relativelyPrime(a: 2, b: 4)) // false

如何判断两个数是否互质？

How to find out if two numbers are relatively prime?

java

primes