Статья Автор: Деникина Н.В., Деникин А.В.

Обработка целых чисел. Пример с большими числами

Задача

Найдите все натуральные числа, принадлежащие отрезку [77777777; 88888888], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым).
В ответе перечислите найденные числа, справа от каждого числа запишите его наименьший нечётный делитель, не равный 1.
 
Решение
Простой перебор всех чисел и подсчет числа делителей будет занимать некоторое время (порядка 20 минут). Поэтому, воспользуемся знаниями из области математики.
 
Любое натуральное число можно представить в виде произведения простых множителей: 
n = p1k1p2k2...pmkm.
Здесь pi (i=1, ...m) – различные простые делители, а ki (i=1, ..., m) – их кратности (натуральные числа).
 
Каждый делитель числа представляется как произведение некоторых или всех простых множителей числа в различных степенях Поэтому, все делители числа (кроме 1) можно получить, взяв произведения всевозможных комбинаций простых множителей. Например, 18 = 2·32. Делители числа 18 – это 1 и 2, 3, 2·3=6, 3·3=9, 2·32=18.

Допустим, в разложение числа на простые множители входит ровно два простых нечётных числа каждое в первой степени: n = 2kp1p2. Тогда число n делится на 1, p1, p2 и произведение p1p2 - всего 4 нечётных делителя. А нам нужно 5. 

Попробуем взять одно из простых чисел во второй степени:  n = 2kp12p2. Тогда нечётными делителями числа n будут: 1, p1, p2, p12, p1p2, p12p2. Всего 6 делителей (больше чем нам нужно). Очевидно, что при увеличении количества нечётных простых делителей мы также получим больше 5 нечётных делителей исходного числа.

Вывод: если число имеет ровно 5 нечётных делителей, в его разложение на простые множители может входить только одно нечётное простое число. Тогда этими делителями будут 1, p, p2, p3, p4, а само число имеет вид n = 2kp4, где k – натуральное число или ноль, p – нечётное простое число.
 
Алгоритм
  1. Перебрать все числа из заданного отрезка.
  2. Убрать из разложения все множители вида (2k) - пока число четное, будем уменьшать его в 2 раза.
  3. Найти, корень четвертой степени из оставшегося числа.
  4. Если оставшееся число является четвертой степенью простого числа, то найдено искомое число.
  5. Для определения наименьшего нечётного делителя, отличного от единицы, используем это найденное простое число.
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать