Поиск ВСЕХ делителей числа (Паскаль)

Запись от Ромаха размещена 21.04.2014 в 22:32

Показов 5022 Комментарии 1

Метки делители, новички, пост-помощь

Никак не думал, что это кому-нибудь пригодится, но, в связи с недавними событиями, пишу этот пост..

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

Итак, собственно, код:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var
    i, n, sq : LongInt;
begin
    ReadLn(n);
 
    sq := Trunc(Sqrt(n) + 0.00001);
    for i := 1 to sq - 1 do begin
        if n mod i = 0 then
            WriteLn(i, '  ', n div i);
    end;
 
    if n mod sq = 0 then
        if n div sq = sq then
            WriteLn(sq)
        else
            WriteLn(sq, '  ', n div sq)
end.

Несколько пояснений:

Сообщение от Новичок

Сообщение от Ромаха

+ 0.00001

Кстати,а это зачем?

Сообщение от Ромаха

Числа в памяти компьютера хранятся приблизительно.. с некой погрешностью.. Посему в некоторый момент времени корень из 4 может стать НЕ 2, а 1.9999999999 и это, заметьте, совершенно верно! А после этого мы Trunc'анем.. и получим 1.. а оно нам надо? Посему я поставил это "магическое" число.. На практике такой феномен встречается достаточно редко.. (а не встречал людей, встречавших такое чудо).. Но чем черт не шутит..

Сообщение от Новичок

Но ведь можно ж использовать Round(sqrt(n))...

Сообщение от Ромаха

Нет нельзя..
999999×1000000 = 999999000000 sqrt(999999000000) = 999999,499999875
А числа еще маленькие.. стоит взять побольше и мы получим, что дробная честь будет стремиться (это пока мои догадки.. никогда не задумывался над доказательством) к 0.5.. и в какой-то момент времени из-за того же феномена.. или из-за маленькой точности оно его достигнет.. тогда Round сделает вот что : Round(sqrt(a*(a+1))) = a+1 и он выведет делители a и a+1 два раза.. что не есть правильно..

Меня, конечно, поразило такое количество вопросов к этому методу.. Поэтому я оставляю этот пост для будущих поколений..

Спасибо за внимание!..

P.S. По поводу оптимальности данного метода.. Он - лучший для небольшого количества маленьких чисел. Если чисел очень много, то можете попробовать решето Эратосфена(Аткина и иже с ними), а если несколько больших, можете прибегнуть к вероятностным алгоритмам.. Правда по названию ясно, что он работает верно не для всех чисел..

Метки делители, новички, пост-помощь

Размещено в Без категории

Главная страница

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 1

Комментарии

Не ищите, не надо, Мы позволяем.

Спасибо, Тсарь-Батюшко. Смилостивились.

Запись от Ромаха размещена 07.07.2017 в 22:58 Ромаха вне форума

Ромаха

Регистрация 16.12.2012
Сообщений 607
Записей в блоге 1

Новые блоги и статьи Все статьи Все блоги /
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .	Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .

Наверх

Сообщение форума

Отменить изменения