В чем же недостаток этого "стандартного" решения?
Такой "прямолинейный" подход не стоит применять, если
- надо найти делители чисел вида pk, поскольку вынуждена перебирать значения до pk/2
- найти все простые делители числа
- проверять большие числа на простоту
Вряд ли, с помощью это подхода, стоит решать и задание следующего типа:
Найдите все натуральные числа, принадлежащие отрезку [525784203; 728943762] и имеющие ровно пять делителей.
Для каждого найденного числа запишите в ответе само число и его наименьший простой делитель.
Найденные числа расположите в порядке возрастания.
Для решения этого и других возможных версий заданий необходимо понимание следствий из основной теоремы арифметики
(это также полезно для решения заданий типа 19 из профильной математики)
Основные свойста следующие:
Если \(N = P_1^{a_1}\cdot . . . \cdot P_k^{a_k},\ где\ все\ P_i - \ различные\ простые\ числа, a_i > 0 \), то
- число \(\Huge{\sigma}_{\large0}\large (N) = (a_1+1)\cdot(a_2+1)\cdot . . . \cdot(a_k+1)\) равно количеству всех делителей числа.
- число: \(\Huge{\sigma}_{\large1}\large (N) = \frac{(P_1^{a_1+1}-1)}{p_1-1}\cdot\frac{(P_2^{a_2+1}-1)}{p_2-1}\cdot . . .\cdot\frac{(P_k^{a_k+1}-1)}{p_k-1}\) равно сумме всех делителей числа
Про вычисление этих чисел
можно см. здесь
Несколько несложных следствий:
- Число N есть квадрат (N = n2) тогда и только тогда, количество его делителей есть нечётное число;
- Если количесто делителей числа N есть простое число k, то N есть k-1 степень простого числа ( N = Pk-1 )
- Если N = 2M, то количество нечётных делителей у чисел N, M одинаковое
Задача. Натуральное число делится на 4, но не делится на 8. Докажите, что сумма его делителей делится на 7
(используйте формулу для суммы делителей и предстваление любого числа в виде 2m*A (A - нечётное)
.