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

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

Показов 5051 Комментарии 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

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

Наверх

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

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