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