相对素数的递归算法

Question

我正在制作一个函数来检查 2 个整数是否互质/互质。函数 returns 如果它们是互质数则为 1，如果它们不是互质数则为 0。

假设 a 和 b 都不为 0，该函数应该能够接受任何顺序的任何整数；

据我所知，gcd 为 -1 与 gcd 为 1 相同。对吗？

这是我的代码：

int relatively_prime(int a, int b){

    if (a == 0 || b == 0) return 0;
    if (a%b == 0 && (b != 1 || b != -1)) return 0;
    else if (a%b== 0 && (b == 1 || b == -1)) return 1;
    else return relatively_prime(b, a % b);
}

这是正确的吗？有什么方法可以简化或改进我的代码吗？

谢谢！

Answer 1

int gcd(int a, int b)
{
    a=abs(a);
    b=abs(b);
    if (b == 0)

        return a;

    return gcd(b, a % b); 

 
}

现在如果结果是 1 它们互质。您可以将负数转换为正数以查看它们是否互素并简化代码。从技术上讲，我们可以将 0 写为 0* 任何数字，因此 0 不会与 1 以外的任何数字互素。

Answer 2

Is this correct?

没有

b != 1 || b != -1 始终为真。所以代码就像

int relatively_prime(int a, int b){
  if (a == 0 || b == 0) return 0;
  if (a%b == 0 /* && (b != 1 || b != -1) */) return 0;
  // a%b== 0 is never true below after the above line
  // else if (a%b== 0 && (b == 1 || b == -1)) return 1;
  else return relatively_prime(b, a % b);
}

... 而不是 return 1.

OP 的代码因 未定义的行为 (UB) 至少在 relatively_prime(INT_MIN, -1) 的情况下失败，因为它尝试 INT_MIN % -1.

Is there any way to simplify ?

// Do not call with gcd_recursive(INT_MIN, -1)
static int gcd_recursive(int a, int b) {
  if (b == 0) return a;
  return gcd_recursive(b, a % b);
}

int relatively_prime_alt(int a, int b) {
  if (b == -1) b = 1; // Avoid a INT_MIN % -1 in gcd_recursive()
  int gcd = gcd_recursive(a, b);
  return gcd == 1 || gcd == -1;
}

相对素数的递归算法

Recursion algorithm for relatively prime integers

c

primes