Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40

Решение по шагам

1. 1

   Как рассуждать

   Решение. Решим задачу перебором. Находя очередной делитель числа, будем проверять, является ли этот делитель нечётным, и, если является, будем прибавлять к переменной count единицу. Также заметим, что у каждого делителя числа есть парный делитель — если он нечётный, будем прибавлять к переменой count единицу. Также учтём то, что у числа может быть 2 одинаковых делителя (например, у числа 9 два одинаковых делителя — числа 3 и 3). Приведём решение на языке Pascal. var count, i, j, k, sqrtI: longint;begin for i := 35000000 to 40000000 do begin count := 0; sqrtI := round(sqrt(i)); for j := 1 to sqrtI do begin if i mod j = 0 then begin if j mod 2 = 1 then count := count + 1; k := i div j; if k mod 2 = 1 then begin count:=count + 1; if j = k then count:=count - 1; end; end; if count > 5 then break; end; if count = 5 then writeln(i); end;end.В результате работы программа должна вывести следующее:35819648389500813903744839337984 Приведем другое решение.

   Число имеет ровно пять нечетных делителей, если оно имеет вид 2ⁿ · p⁴, где p — простое число, n — произвольное натуральное число. В этом случае нечетными делителями числа будут числа 1, p, p², p³ и p⁴. Следовательно, можно искать корень четвертой степени из числа, деленного на максимально возможную степень двойки. Если этот корень четвертой степени является простым числом, то само число имеет ровно пять нечетных делителей. Приведем программу на языке Pascal, реализующую этот способ. var simple, i, j, c, sqrtI: longint;begin for i := 35000000 to 40000000 do begin c:=i; while c mod 2 = 0 do begin c:=c div 2; end; sqrtI := round(sqrt(c)); sqrtI:= round(sqrt(sqrtI)); if sqrtI * sqrtI * sqrtI * sqrtI = c then begin simple:=1; for j:=3 to round(sqrt(sqrtI)) do begin if sqrtI mod j=0 then begin simple:=0; break; end; end; if simple=1 then writeln(i); end; end;end. Приведем математическое обоснование данного способа.

   Пусть разложение числа m на простые множители имеет вид $m=a_0 в степени ( k_0 ) a_1 в степени ( k_1 ) ...a_n в степени ( k_n ) ,$ тогда количество делителей числа m равно $( k_0 + 1 ) \cdot ( k_1 + 1 ) ... ( k_n + 1 )$ В частности, четное число раскладывается на множители как $2 в степени ( k_0 ) a_1 в степени ( k_1 ) ...a_n в степени ( k_n ) ,$ где множители a_i — нечетные числа. Тогда число имеет $( k_0 ) \cdot ( k_1 + 1 ) \cdot ( k_2 + 1 ) ... ( k_n + 1 )$ четных делителей и $( k_1 + 1 ) \cdot ( k_2 + 1 ) ... ( k_n + 1 )$ нечетных.

   По условию задачи требуется, чтобы число имело 5 нечетных делителей. Число 5 можно представить в виде произведения единственным способом 1 · (4 + 1), следовательно, разложение искомого числа на простые множители должно иметь вид 2ⁿ · p⁴. Примечание Никиты Степанова.

   Второй способ решения будет давать неверный результат, если в заданном диапазоне есть число, являющееся степенью двойки. В этом случае получим sqrtI = c = 1, цикл проверки делимости числа не выполнится ни разу, и переменная simple останется равной