Найти число, сумма делителей которого в три раза больше самого числа - QBasic
Формулировка задачи:
Найти число, сумма делителей которого в три раза больше самого числа
(Само число к делителям не относится)
Программа нашла наименьшее из таких чисел - 30240
примечание
Тут бейсику пришлось посчитать. Вероятнее всего он никогда не найдет
числа, сумма делителей которого в 4 раза, (в 5 раз) больше самого числа...
Решение задачи: «Найти число, сумма делителей которого в три раза больше самого числа»
textual
Листинг программы
{$mode objfpc}
uses windows;
type
Tlong = qword;
const
n = 50;
var
f : array [1 .. n] of
record
mult : integer;
power : integer;
end;
// I variant
function ds(i : longint) : longint;
var j : longint;
begin
result := 0;
for j := 1 to i div 2 do
if i mod j = 0 then result := result + j;
end;
procedure Add(i : integer);
var
j : integer;
found : boolean;
begin
found := false; j := 1;
while (j <= n) and (f[j].mult > 0) and (not found) do
if f[j].mult = i then
begin
inc(f[j].power); found := true;
end
else inc(j);
if not found then
begin
f[j].mult := i; f[j].power := 1;
end;
end;
function Factorization(x : Tlong) : Tlong;
var i : Tlong;
procedure DivX;
begin
while (x > 1) and (x mod i = 0) do
begin
Add(i); x := x div i;
end;
end;
var
j, k : integer;
t, s : Tlong;
begin
i := 2;
DivX;
i := 3;
while i < x div 2 do
begin
DivX;
inc(i,2);
end;
if x > 1 then Add(x);
k := 1;
result := 1;
while (k <= n) and (f[k].mult > 0) do
begin
// write(f[k].mult, '^', f[k].power, ' ');
t := 1; s := 1;
for j := 1 to f[k].power do
begin
t := t * f[k].mult;
s := s + t;
end;
result := result * s;
inc(k);
end;
end;
var
p, num : Tlong;
i : integer;
tm : dword;
begin
tm := gettickcount;
num := 2;
repeat
inc(num, 2);
FillByte(f, sizeof(f), 0); // обнуляем массив структур
p := Factorization(num);
until(p = 4 * num);
writeln(num, ': sum of divisors = ', p, ' vs ', 4 * num);
writeln('time = ', gettickcount - tm);
// сравниваем с твоим методом вычисления суммы делителей
tm := gettickcount;
for i := 1 to 20000 do
if ds(2*i) = 3 * 2*i then
begin
writeln(2*i); break;
end;
writeln('time = ', gettickcount - tm);
readln;
end.
Объяснение кода листинга программы
- В первой строке объявлен массив структур с двумя полями: mult и power.
- Далее идет функция ds, которая вычисляет сумму делителей числа i.
- После этого идет процедура Add, которая добавляет число i в массив f, если оно еще не присутствует.
- Затем идет функция Factorization, которая вычисляет факторизацию числа x.
- В основной части кода идет поиск числа, для которого сумма делителей равна 4 разам самого числа.
- В конце кода идет сравнение с другим методом вычисления суммы делителей и выводится время выполнения.