Найдите все натуральные числа N, принадлежащие отрезку [400 000 000; 600 000 000], которые можно представить в виде N = 2m · 3n, где m — чётное число, n — нечётное число. В ответе запишите все найденные числа в порядке возрастания.
Ответ:
Решим задачу перебором. Сгенерируем числа, подходящие под условия задачи. Массив arr2 заполним числами, которые являются чётными степенями двойки, то есть 20, 22, 24 и так далее. А
Приведём решение на языке Pascal.
var
arr2: array[1..30] of int64;
arr3: array[1..20] of int64;
answer: array[1..100] of int64;
t: int64;
i, j, k: integer;
begin
arr2[1] := 1;
arr3[1] := 3;
for i := 1 to 100 do answer[i] := 0;
for i := 1 to 29 do arr2[i+1] := arr2[i] * 2 * 2;
for i := 1 to 19 do arr3[i+1] := arr3[i] * 3 * 3;
for i := 1 to 30 do
for j := 1 to 20 do begin
if ((arr2[i] * arr3[j]) >= 400000000) and ((arr2[i] * arr3[j]) <= 600000000) then
for k := 1 to 100 do
if answer[k] = 0 then begin
answer[k] := arr2[i] * arr3[j];
break;
end;
end;
for i := 1 to 100 do
for j := i + 1 to 100 do
if answer[i] > answer[j] then begin
t := answer[i];
answer[i] := answer[j];
answer[j] := t;
end;
for k := 1 to 100 do
if answer[k] <> 0 then writeln(answer[k]);
end.
В результате работы программа должна вывести следующее:
408146688
452984832
516560652
573308928
Приведем решение Миши Бурмистрова.
Будем делить каждое число из заданного диапазона
var i,j,m,n:longint;
begin
for j:=400000000 to 600000000 do begin
i:=j;
m:=0;
n:=0;
while i mod 2 = 0 do begin
i:=i div 2;
m:=m+1;
end;
if (m mod 2 = 0) then begin
while i mod 3 = 0 do begin
i:=i div 3;
n:=n+1;
end;
if (n mod 2 <> 0) and (i=1) then writeln(j);
end;
end;
end.
Заметим, что время работы данной программы можно уменьшить на основе следующих соображений. Если число делится на четную степень двойки, значит, оно делится на некоторую степень четверки, поэтому число можно делить
var i,j,m,n,k:longint;
begin
j:=40000008;
repeat
i:=j;
k:=0;
n:=0;
while i mod 4=0 do begin
i:=i div 4;
k:=k+1;
end;
if k>0 then begin
while i mod 3 = 0 do begin
i:=i div 3;
n:=n+1;
end;
if (n mod 2 <> 0) and (i=1) then writeln(j);
end;
j:=j+12;
until j>=600000000;
end.
Приведём другое решение Боголюбова Ивана на языке Pascal.
var
p:biginteger;
count,m,n:integer;
begin
count:=0;
for m:=2 to 28 do
if (m mod 2)=0 then begin
for n:=1 to 18 do
if (n mod 2)<>0 then begin
p:=biginteger.Pow(2,m)*biginteger.Pow(3,n);
if (p>=400000000) and (p<=600000000) then begin
inc(count);
println(p);
end;
end;
end;
end.
Приведём решение на языке Python.
for j in range(400000000, 600000000 + 1):
i = j
m = 0
n = 0
while i % 2 == 0:
i //= 2
m += 1
if m % 2 == 0:
while i % 3 == 0:
i //= 3
n += 1
if n % 2 != 0 and i == 1:
print(j)
Приведём решение Морёнова Сергея на языке Python.
a=[]
for m in range(0,30,2):
for n in range(1,20,2):
x = 2**m * 3**n
if 400000000<= x <=600000000:
a.append(x)
print(*sorted(a))
Приведём решение Юрия Красильникова на языке Python.
nums = [2**m*3**n for m in range(0,30,2) for n in range(1,30,2) if 400000000 <= 2**m*3**n <= 600000000]
for n in sorted(nums): print(n)