GCD逻辑错误

Question

我写这段代码是为了在 c 中获取 gcd。它非常适合小数字但是当我尝试 60 和 90 时，我得到了 2，而 9 和 6 得到了 3。

#include "stdio.h"
#include "stdlib.h"
int main()
{
    int a,b,x,gcd;
    printf("Please Enter the fraction");
    scanf("%d", &a);
    scanf("%d", &b);
    if(b%a == 0)
        gcd =a;
    else
    {
        x=a;
        while(--x>1)
        {
            if (a%x == 0 && b%x==0)
            {  
                 gcd =x;
            }
        }
    }
    printf("GCD = %d", gcd);
    return 0;
}

Answer 1

如果第二个 if 中的条件为真，则需要中断循环。只需在第二个 if:

的正文中添加 break;

if (a%x == 0 && b%x==0)
  gcd =x;

应该是

if (a%x == 0 && b%x==0)
{
  gcd =x;
  break;
}

否则继续循环并找到大于 1 的最小公约数。

Answer 2

#include "stdio.h"
#include "stdlib.h"
int main()
{
    int a,b,x,gcd;
    printf("Please Enter the fraction");
    scanf("%d", &a);
    scanf("%d", &b);
    if(b%a == 0)
        gcd =a;
    else
    {
        x=a;
        while(--x>1)
        {
            if (a%x == 0 && b%x==0){
                gcd =x;
                break;
            }
        }
    }
    printf("GCD = %d", gcd);
    return 0;
}

问题是当你找到gcd时你必须打破循环 //否则你可以使用这个递归函数

int gcd(int a, int b) {
    if ( a == 0 ) {
        return b;
    } else {
        return gcd(b%a, a);
    }
}

GCD逻辑错误

GCD logical error

c

greatest-common-divisor