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

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

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

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

Наверх

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

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