Поиск делителей числа

← →
cr@nk © (2008-01-25 09:14) [0]

Условие задачи: Составить программу для графического изображения делимости чисел от 1 до n. В каждой строке напечатать очередное число и столько символов «+», сколько делителей у этого числа: 1+ 2++ 3++ 4+++

Собственно саму задачу решил, но препод настаивает на решении более оптимальным способом (без использования массивов, это я просто на всякий случай уточняю)

var i, j, x, k: Word; begin Write("Vvedite cheslo: "); Readln(x); for I := 1 to x do begin k := 0; Write(i); for j := 1 to i do begin if i mod j = 0 then Write("+"); end; Writeln; end; Readln end.

Собственно надо эту часть for j := 1 to i do оптимизировать. Говорят, что надо использовать корень числа (например для 20 корень из 20), но я не могу понять как

← →
Семеныч (2008-01-25 09:25) [1]

Максимальный делитель числа не может быть больше корня из этого числа. Значит, незачем гнать цикл до самого числа, достаточно до корня из него.

for j := 1 to Trunc(Sqrt(i)) do ...

← →
oldman © (2008-01-25 09:25) [2]

> Собственно надо эту часть for j := 1 to i do оптимизировать.
>

for j:=1 to i/2
Число не может делиться на число, которое больше его половины без остатка
:)))

← →
oldman © (2008-01-25 09:26) [3]

> Семеныч (25.01.08 09:25) [1]
> Максимальный делитель числа не может быть больше корня из
> этого числа.

У 10, например, есть делитель 5

← →
cr@nk © (2008-01-25 09:29) [4]

Спасибо. Что-то я не догадался сразу про это свойство

> for j:=1 to i/2

Малость ошибочная запись... число должно быть целочисленным ;)

← →
Семеныч (2008-01-25 09:31) [5]

> oldman © (25.01.08 09:26) [3]

... который должен быть найден одновременно с делителем 2.

← →
Sergey13 © (2008-01-25 09:46) [6]

Да иначинать цикл можно с 2, а не с 1. 8-)

← →
oldman © (2008-01-25 09:46) [7]

Значит, оптимизация такая:

for j := 1 to Trunc(Sqrt(i)) do
...
Write("++");
...

Только обдумать:
Если корень круглый, write("+") для корня...
Например 9 делится на 3, остаток 3

← →
oldman © (2008-01-25 09:47) [8]

> Sergey13 © (25.01.08 09:46) [6]
> Да иначинать цикл можно с 2, а не с 1. 8-)

Нет.
Для 1 тоже надо Write("++"), поскольку число делится на 1 и на самое себя

> [8] oldman © (25.01.08 09:47)
> Для 1 тоже надо Write("++"), поскольку число делится на
> 1 и на самое себя

Я имел в виду, что это можно и не анализировать IF-ом. Просто рисовать плюсик.

var
i, j, x, k: Word;
begin
Write("Vvedite cheslo: ");
Readln(x);
for I := 1 to x do
begin
k := 0; А вот это зачем???
Write(i);
for j := 1 to Trunc(Sqrt(i)) do
begin
if i mod j = 0 then
Write("+");
if j<Trunc(Sqrt(i)) Write("+");
end;
Writeln;
end;
Readln
end.

> Просто рисовать плюсик.

Два плюса, если число больше 1

Поиск делителей числа Найти похожие ветки