Подсчет количества делителей больших чисел

Эта тема является частью раздела целочисленных свойств в Quant GMAT Focus.

Рассмотрим типичный экзаменационный вопрос:

Сколько делителей имеет число 8400?

Для небольших чисел (меньше 100) можно просто выписать пары множителей. Но для больших чисел такой подход слишком медленный и не подходит для экзамена. К счастью, существует стандартная и очень быстрая процедура, которую GMAT и GRE ожидают от вас.

Универсальная процедура из четырех шагов

Шаг 1. Найти разложение на простые множители

Начинаем с разложения числа на простые множители и обязательно приводим его к виду произведения степеней простых чисел.

Пример для 8400:

• 8400 = 84 × 100
  
  
• 84 = 7 × 12
  
  
• 12 = 3 × 4 = 3 × 2 × 2
  
  
• 100 = 10 × 10 = 2 × 5 × 2 × 5
  
  

Собираем все множители:

• 8400 = 2 в четвертой степени × 3 × 5 в квадрате × 7
  
  

Шаг 2. Выписать показатели степеней

Теперь выписываем показатели степеней каждого простого множителя.

Важно: если степень не указана, она равна 1.

Для 8400:

• 2 → степень 4
  
  
• 3 → степень 1
  
  
• 5 → степень 2
  
  
• 7 → степень 1
  
  

Список степеней:
4, 1, 2, 1

Шаг 3. Прибавить 1 к каждому показателю

К каждому числу в списке прибавляем 1:

• 4 + 1 = 5
  
  
• 1 + 1 = 2
  
  
• 2 + 1 = 3
  
  
• 1 + 1 = 2
  
  

Новый список:
5, 2, 3, 2

Шаг 4. Перемножить числа из нового списка

Перемножаем все значения:

• 5 × 2 × 3 × 2 = 60
  
  

Ответ:

Число 8400 имеет 60 делителей.

В их числе обязательно есть:

• 1 (делитель любого числа)
  
  
• само число 8400
  
  

Повторим алгоритм кратко

Чтобы найти количество делителей положительного целого числа N:

1. Найти разложение N на простые множители
   
   
2. Выписать показатели степеней
   
   
3. Прибавить 1 к каждому показателю
   
   
4. Перемножить полученные числа
   
   

Результат — общее количество делителей N.

Еще один пример: число 21 600

Задача: сколько делителей у числа 21 600?

Шаг 1. Разложение на простые множители

• 21 600 = 216 × 100
  
  

Разложим 216:

• 216 = 6 × 6 × 6
  
  
• 6 = 2 × 3
  
  

Следовательно:

• 216 = 2 в третьей степени × 3 в третьей степени
  
  

Разложение 100:

• 100 = 2 × 5 × 2 × 5 = 2 в квадрате × 5 в квадрате
  
  

Собираем всё вместе:

• 21 600 = 2 в пятой степени × 3 в третьей степени × 5 в квадрате
  
  

Шаг 2. Список показателей степеней

Показатели:

• 2 → 5
  
  
• 3 → 3
  
  
• 5 → 2
  
  

Список:
5, 3, 2

Шаг 3. Прибавляем 1

• 6, 4, 3
  
  

Шаг 4. Перемножаем

• 6 × 4 × 3 = 72
  
  

Ответ:

Число 21 600 имеет 72 делителя.

Подсчет количества нечетных и четных делителей

Количество нечетных делителей

Чтобы найти число нечетных делителей, нужно:

• полностью игнорировать множитель 2
  
  
• учитывать только нечетные простые множители
  
  

Для 21 600:

• игнорируем 2 в пятой степени
  
  
• остаются показатели: 3 (для 3) и 2 (для 5)
  
  

Добавляем 1:

• 4 и 3
  
  

Перемножаем:

• 4 × 3 = 12
  
  

Нечетных делителей — 12.

Количество четных делителей

Прямой формулы нет. Используем вычитание:

• всего делителей: 72
  
  
• нечетных делителей: 12
  
  

Четных делителей = 72 − 12 = 60

Почему этот метод работает (концептуально)

Разложение на простые множители показывает все возможные «строительные блоки» числа.

Для числа:

• 21 600 = 2 в пятой степени × 3 в третьей степени × 5 в квадрате
  
  

Любой делитель этого числа:

• может содержать от 0 до 5 двоек → 6 вариантов
  
  
• от 0 до 3 троек → 4 варианта
  
  
• от 0 до 2 пятерок → 3 варианта
  
  

Каждый выбор независим от остальных, поэтому:

• 6 × 4 × 3 = 72 возможных делителя
  
  

Выбор:

• 0, 0, 0 дает делитель 1
  
  
• 5, 3, 2 дает само число 21 600
  
  

Все остальные комбинации дают остальные делители.

Итоги

В этой главе мы разобрали:

• эффективный метод подсчета делителей больших чисел
  
  
• пошаговый алгоритм из четырех шагов
  
  
• применение метода к реальным экзаменационным числам
  
  
• способ подсчета нечетных и четных делителей
  
  
• концептуальное объяснение, почему метод работает
  
  

Этот навык крайне важен для GMAT и GRE и будет многократно использоваться в задачах на делимость, множители и разложение чисел.