C ++ Наименьший общий переписывающий делитель

Question

Я сделал функцию, которая возвращает наименьший общий делитель из 2 чисел.

int check (int a, int b)
{
 int i = 2; //every number is divisible by 1
   begin:
    if ((a % i == 0) && (b%i == 0)) //i must be divisible by both numbers
      {
         return i;
      }
    else
      {
          i++;
          goto begin;
      }
}

Однако я использую очень рекомендованный метод goto, поэтому мне было интересно, как это можно переписать, используя для или в то время как цикл .

Answer 1

Если a и b взаимно просты (gcd = 1), ваш алгоритм завершится только после того, как я переполнится и достигну -1. т.е. после 4 миллиардов итераций.

И даже если это не тот случай, ваш алгоритм медленный (линейный в gcd (a, b)). Вы должны взглянуть на евклидов алгоритм , который намного быстрее.

Ваш код в переписанном виде (проблема с завершением не устранена), поэтому он эквивалентен вашему старому коду:

int check (int a, int b)
{
 int i = 2; //every number is divisible by 1
   while(!((a % i == 0) && (b%i == 0)))//i must be divisible by both numbers
   {
      i++;
   } 
   return i;
}

Переписано в цикл for, который завершается, когда становится ясно, что gcd == 1

int check (int a, int b)
{
  for(int i=2;i<=Math.Min(a,b);i++)
  {
    if((a % i == 0) && (b%i == 0))
      return i;
  }
  return 1;
}

Answer 2

int check (int a, int b)
{
    for(int i = 2; i < min(a,b); i++)
        if ((a % i == 0) && (b%i == 0)) //i must be divisible by both numbers
            return i;
    return 1;
}

Где min() ... ну, вы понимаете это ...

Answer 3

for(int i = 2; (a % i != 0) || (b%i != 0); ++i)
{
    if( i > a || i > b)//a and b are prime
        return 1;
}
return i;

Answer 4

while(i < min(a, b)) {
     ...
}

Приходит в голову ... Как только я больше, чем a или b, нет смысла идти дальше.

Есть еще одна проблема в вашем коде, если a и b оба простые, это будет бесконечный цикл;)

РЕДАКТИРОВАТЬ: очень важно понимать, что вы не можете использовать делимость в качестве условия остановки, в противном случае это может привести к бесконечному циклу, когда оба числа просты, или если у них нет общего делителя.