Разложение числа на множители. Не ясно зачем ведется одна проверка

#c_sharp #алгоритм

Есть код на C# разложения числа на множители. Понимаю весь код, кроме строчки:


if (n / b * b - n == 0)



Что проверяет данная строчка? Ведь  пы просто получаем ноль, зачем тогда она нужна?

using System;

namespace ExpandNumberForum
{
  class Program
  {
    public static void Main(string[] args)
    {
        string s = string.Empty;
        int b, c, n;

        Console.WriteLine("Input number: ");
        if (!int.TryParse(Console.ReadLine(), out n)) return;

        while ((n % 2) == 0)
        {
            n = n / 2;
            s += "2*";
        }
        b = 3; c = (int)Math.Sqrt(n) + 1;
        while (b < c)
        {
            if ((n % b) == 0)
            {
                if (n / b * b - n == 0)
                {
                    s += b.ToString() + "*";
                    n = n / b;
                    c = (int)Math.Sqrt(n) + 1;
                }
                else
                    b += 2;
            }
            else
                b += 2;
        }
        s += n.ToString();
        Console.WriteLine(s);

        Console.Write("Press any key to continue . . . ");
        Console.ReadKey(true);
    }
}
}

    

Ответы

Ответ 1

Эта строчка проверяет, что n нацело делится на b. 

То есть делает то же самое, что (n % b) == 0.

if с проверкой n / b * b - n == 0 - лишний.



function dividers(n) {
  var s = [];
  var b;
  var c;

  while ((n % 2) == 0) {
    n = n / 2;
    s.push(2);
  }
  b = 3;
  c = Math.floor(Math.sqrt(n)) + 1;
  while (b < c) {
    if ((n % b) == 0) {
      s.push(b);
      n = n / b;
      c = Math.floor(Math.sqrt(n)) + 1;
    } else
      b += 2;
  }
  s.push(n);
  return s;
}

console.log(JSON.stringify(dividers(621756)));


Ответ 2

Оператор / выполняет целочисленное деление, т.е. деление с остатком, c округлением
частного к нулю до целого. По этой причине в общем случае a / b * b не равно a. Равенство
будет выполняться только в том случае, если a нацело делится на b.

В "студенческом" коде часто встречается использование следующей техники вычисления
остатка r от деления a на b

r = a - a / b * b


(до того, как студентам расскажут про существование оператора %, а также и после).

Именно это вы и видите в данном коде. Проверка n / b * b - n == 0 - это проверка
того, что остаток от деления n на b равен 0, т.е. того, что n нацело делится на b.
Эквивалентно можно было написать n / b * b == n, но лучше, конечно, воспользоваться
оператором % и просто проверить n % b == 0.



Как правильно заметил @Igor в своем ответе, проверять n / b * b - n == 0 после уже
выполненной эквивалентной проверки n % b == 0 - совершенно бессмысленный шаг.