Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 2.

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

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

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

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

Итак, собственно, код:
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. По поводу оптимальности данного метода.. Он - лучший для небольшого количества маленьких чисел. Если чисел очень много, то можете попробовать решето Эратосфена(Аткина и иже с ними), а если несколько больших, можете прибегнуть к вероятностным алгоритмам.. Правда по названию ясно, что он работает верно не для всех чисел..
Размещено в Без категории
Просмотров 1039 Комментарии 1
Всего комментариев 1

Комментарии

  1. Старый комментарий
    Аватар для Ромаха
    Цитата:
    Не ищите, не надо, Мы позволяем.
    Спасибо, Тсарь-Батюшко. Смилостивились.
    Запись от Ромаха размещена 07.07.2017 в 22:58 Ромаха вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.