сокращение числа переборов для нахождения делителей числа

[ujif]

Здравствуйте
дано натуральное число,нужно найти все его делители(тоже натуральные числа)
до минимума сократив количество перебираемых чисел.
пример: зная что число делится только на 2 и 3 ,например число 36,
как сократить перебор,не используя оператор for
делителями числа 36 является следующая последовательность цифр 1,2,3,4,6 или посложнее -
делителями числа 108 являются 1,2,3,4,6,9 вот кусочек программы

readln(x);
if (x mod 2=0) and (x mod 3=0) and (x mod 5<>0) and (x mod 7<>0) then
begin
while trunc(sqrt(x))>=y do begin

икс-это натуральное число для которого нужно найти делители(тоже натуральное числа)
игрек- это делители числа икс
интересует,как можно вывести эти цифры 1,2,3,4,6,9 не прибегая к
оператору for так как для больших значений икс время перебора с for
значительно увеличится
желательно не решать за меня ,а просто указать правильное направление
куда думать (если конечно есть такое)

[Poma][a]

Конечно можно что-то придумать с массивом, простыми числами, etc..
Но т.к. сегодняшнее машины могут делать опупенное кол-во операций, то,наверное, нам хватит сложности O (Sqrt(n))
Тоесть

var
     n, i : LongInt;

begin
     ReadLn (n);
     
     for i := 1 to Round(Sqrt(n)) do
          if n mod i = 0 then
              WriteLn (i, ' ', n div i)

end.

Вот делители миллиона считаются за 0,02 секунды.. тыц

[s-andriano]

Сообщение от ujif

пример: зная что число делится только на 2 и 3 ,например число 36,

Если число делится только на 2 и 3, это значит, что ни на какие другие числа оно больше не делится, и 2 и 3 и является полным списком его делителей. Но таких числе в природе не существует, т.к. любое число, которое делится на 2 и 3, одновременно делится и на 6.
А случай с числом 36 - вообще интересный: среди его делителей присутствует число 4, т.е. 36 не просто делится на 2, а делится на 2 дважды, что приводит с совершенно другим результатам.

Подозреваю, что Вам нужно сначала разложить число на простые делители (для 36 это будет 2,2,3,3 - обратите внимание, что некоторые числа входят более одного раза), а потом просто получить все возможные произведения этих простых делителей (чисто комбинаторная задача).

[alexander13]

Сообщение от s-andriano

Подозреваю, что Вам нужно сначала разложить число на простые делители (для 36 это будет 2,2,3,3 - обратите внимание, что некоторые числа входят более одного раза), а потом просто получить все возможные произведения этих простых делителей (чисто комбинаторная задача).

Бессмысленно. Если применять простые алгоритмы факторизации, типа перебора делителей, то сложность так и останется порядка корня из N. Более сложные алгоритмы вряд ли ему подойдут. Да и весь выигрыш (если таковой будет) от них, убьется получением "всех возможных произведений".

[Slym]

без цикла - рекурсией

[s-andriano]

Сообщение от alexander13

Бессмысленно.

Бессмысленно говорить "бессмысленно" до того, как для данной задачи будет определено, в чем именно состоит смысл.
Если под словом "сокращение" подразумевается какая-либо оптимизация, то необходимо сформулировать критерии этой оптимизации.
Ну а заодно вычснить, что же требуется получить.
Например, для числа 36 делителями являются 12 и 18, о которых ТС почему-то не упоминает. Почему?

[Poma][a]

Хм.. интересные дебаты

var
        i, n : Integer;

begin
        ReadLn (n);

        i := 2;

        while n >= i do
                if n mod i <> 0 then
                        Inc(i)
                else begin
                        Write (i, ' ');
                        while n mod i = 0 do
                                n := n div i
                end
end.

Вот есть алгоритм разложения на множетели, его сложность :

А теперь еще полный перебор этих множителей и поиск их произведений.. Если мы и получим оптимизацию, то она будет настолько мала, что для массива в миллион чисел, мы едва почувствуем эту разницу..

Александр, плюсую, ан нет! Не дает

[ujif]

пожалуйста объясните как у Вас получается
писать код именно так аккуратно ,я не нашел никаких
тегов чтобы мой код можно было также выделить

[Poma][a]

Пишете код, выделяете его и тыкаете кнопочку с #. Или ручками вписываете его в теги [СODE] [/CODE]