|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
25.07.2018, 11:27 | #1 |
Новичок
Джуниор
Регистрация: 25.07.2018
Сообщений: 6
|
Быстрый код поиска чисел не делящихся.
Привет!
У меня такая проблема: мне надо сделать программ который для двоих числ ("a" и "b") сказать сколько между ними числ (с ними тоже) которые не делится на никакого числа из данного множества. Как это сделать быстрее? Я сделал такой вот код: Код:
Извини за мой русский - я не росиянин. |
25.07.2018, 11:52 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
я бы не использовал multiset
просто в цикле проверял делимость. но у меня вопрос. ведь a и b не подходят по условию (не подходят, потому что а делится на a, а число b делится на b), поэтому их не считаем, так ? какой ответ, например, для диапазона 3 7 ? ответ 2 ? (это числа 4, 5) ? такой вариант не устроит? Код:
Последний раз редактировалось Serge_Bliznykov; 25.07.2018 в 11:58. |
25.07.2018, 12:18 | #3 |
Новичок
Джуниор
Регистрация: 25.07.2018
Сообщений: 6
|
Нет, нет, ты мне не понял. Мне надо сказать сколько в промежутком [a,b], которые не делятся та никакого число с донного множества (данный он есть во время активности программа).
Примеры: 1: set = {1} range = [3, 7] out = 0 (нет числ которые не деляются на 1) 2: set = {2,3} range = [3,7] out = 2 (толькл 5 и 7 не делаются на 2 и 3) 3: set = {5, 11, 8} range = [1,100] out = 63 (63 числ в [1,100] которые не делятся на 5, 11 и 8) 4: set = {4, 3, 5, 7} range = [1,100] out = 34 принятие: все числа в set и range будут натуральные Последний раз редактировалось Tulio; 25.07.2018 в 12:21. |
25.07.2018, 12:21 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
В multiset-е же заданный список делителей, его не отбросишь )
А что под ускорить имеется в виду? Получилось ~0.5 сек для чисел по ссылке делфийской прогой, а сколько нужно? add для начала можно проверить четность делимого и делителя, и не проверять остаток от деления, если делимое не четное, а делитель четный например
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 25.07.2018 в 12:29. |
25.07.2018, 12:27 | #5 |
Новичок
Джуниор
Регистрация: 25.07.2018
Сообщений: 6
|
Да. Где возможно искать ускорения знаю: multiset данный раз, а range-ов может быть бесконечное количество и поэтому я бы хотел сделать то так что если кто-то искает похоже range это будет быстрее, например:
range = [1, 1000] а потом: range = [3,500] думаю что другого можно бы не вычислять. Но не знаю как. или: range = [1,1000] а потом: range = [700,1100] должен быть способ чтобы 700-1000 не делать второй раз. |
25.07.2018, 12:35 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Есть же максимальный диапазон range. Если он не очень большой, то можно массив держать, соответствующей размерности, в котором отмечать проверялось ли число и, если проверялось, то есть ли для него делитель в списке делителей.
add Попробовал, в 5 раз быстрей стало для того набора чисел Четность не проверял, возможно еще чуть-чуть можно ускорить
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 25.07.2018 в 12:44. |
25.07.2018, 12:44 | #7 |
Новичок
Джуниор
Регистрация: 25.07.2018
Сообщений: 6
|
Как это хорошо сделать? Максимальный range (сейчас, но если будет больший то не очень) это [1,10^6].
|
25.07.2018, 12:54 | #8 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Массив байтов соответствующего размера. Индекс соответствует числу из диапазона. Массив инициализировать нулем. Если 0 - проверка и заполнение 1 или 2, если 1 - нет делителей, 2 - есть
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
25.07.2018, 13:12 | #9 |
Новичок
Джуниор
Регистрация: 25.07.2018
Сообщений: 6
|
Да. Теперь код:
Код:
Ещё подумал что можно сделать сортировку числ из multiset потому что это больше правдоподобие, что 2 будет делить данное число тем например 125. Хорошо думаю? Пожалуй только можно ещё сделать. |
25.07.2018, 13:25 | #10 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
numbers[i] == 2 можно и не проверять, достаточно сравнить с 1 и 0
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Сумма всех трехзначных чисел, не делящихся ни на 5, ни на 7 на Prolog | abc7 | Помощь студентам | 2 | 27.12.2016 13:49 |
Найти количество трёхзначных чисел делящихся на 7 и не делящихся на 3 | TsykunovDmitriy | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 07.05.2014 23:05 |
код поиска чисел Фибоначчи | sam5213 | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 20.03.2012 23:17 |
Количество чисел, делящихся на 11 | CrazyRabbit | Помощь студентам | 9 | 09.08.2009 01:56 |
Вывод чисел, делящихся на каждую из своих цифр. Паскаль | ЯншинаВера | Помощь студентам | 3 | 08.04.2008 11:50 |