[code python][/code]
a = 35000000 b =40000000 k = 0 for n in range(a, b + 1): ds = [] for d in range(1, n,2): if n % d == 0: ds.append(d) if len(ds)>5: break if len(ds) == 5: print(n)
Полная версия: Задача из егэ по информатике
.
Спасибо, что подсказали. Не знаете как решить такую задачу?
Lee1.Так тут не в коде дело, а математике. Очевидно что не нужно перебирать все делители от1 до n
Если да, то кому не сложно напишите пожалуйста код…. Можно ли как нибудь ускорить этот процесс?
for d in range(1, n,2):
Во вторых на само себя оно делиться со 100% вероятностью, я гарантирую вам это. Тоесть вам только нужно лпределить четное оно или нет, если не четное то +1 к колличеству нечетных делителей.
В третих очевидно что число не может быть поделено нацело если делитель больше чемполовина этого числа. При этом четные делители вас не интересуют.
По итогу вы может брать только нечетные числа начиная с тройки и заканчивая n//3+1, что уменшит количество необходимых операций
Возможно если не делить на3, 5, 9, а воспользваться признаками деления на 3, 5, 9 то оно еще будет быстрее, всеже операция деления затратнее чем сравнения и/или сложения. Но тут нужно уже смотреть.
PEHDOM
1) Можно применить решето Эратосфена и из искомого диапазона вычеркнуть сразу все простые числа, чтобы не тратить время на проверку каждого из них на множественные делители.
2) Может стоит искать делители не последовательно, а рассматривать четность/нечетность делимого, делителя и частного.
Тут же не сказано в условии, что именно 5 наименьших делителей
Потенциальные делители тогда сверху сможем ограничить корнем квадратным из делимого, а значит еще сократить перебор.
Если число делится на 2 без остатка, то частное может быть четным и нечетным.
Например, 35000002 поделенное на 2 это 17500001. Получается, что при делении на 2 мы нашли один из искомых нечетных делителей. Но при этом каждый раз нам надо проверять четность частного, а это дополнительная операция.
Так же может стоит для оптимизации алгоритма рассмотреть является ли делимое четным числом или нет, чтобы еще сузить круг потенциальных делителей.
Что мы имеем:
1) четное / четное - не можем судить о нечетности результата: может быть четным и нечетным
Следовательно, четные делимые имеет смысл проверять на деление на 2 и на степени числа 2.
Степенями двойки выявим делители типа таких 35000000 / 64 что дает 546875
2) четное / нечетное - если делится нацело, то результат всегда четный.
3) нечетное / четное - результат не будет целым числом. Следовательно, нечетные делимые нет смысла гонять по набору четных делителей.
4) нечетное / нечетное - если результат целое число, то нечетное. Следовательно, в этом случае наш счетчик нечетных делителей получает сразу +2 найденных нечетных делителя. Здесь даже контролировать четность частного дополнительной операцией не нужно.
В итоге имеем:
ШАГ 1: Выявляем и сохраняем массив простых чисел из искомого диапазона с помощью решета Эратосфена
ШАГ 2: проверяем делимое на четность. Тут е
Для нечетных делимых:
ШАГ 3: Проверяем есть ли это делимое в нашем массиве простых чисел или нет. Если нет, то:
ШАГ 4: Проверяем делимость на нечетные числа, которые меньше или равны корню квадратному из делимого. Помним, что каждый найденный делитель нам дает +2 к счетчику. Если не набрали искомое число делителей, то ответ “Нет”, если набрали - “Да”
Для четных делимых:
ШАГ 3: Проверяем делимость на нечетные числа, которые меньше или равны корню квадратному из делимого, при этом контролируем четность остатка, чтобы не пропустить комбинацию нечетное х нечетное = четное. Если нашли нужное количество делителей, выводим “да”, иначе шаг 4
ШАГ 4. Дополнительно проверяем четными делителями, а именно степенями числа 2. Если так и не нашлись, то выводим “Нет”, если нашлись, выводим “Да”.
Чтобы каждый раз не строить ряд нечетных делителей и степеней числа 2, их тоже можно вынести в отдельный шаг и сохранить как массив чисел. Рассчитать их до корня квадратного верхней границы диапазона включительно.
Так как я всегда в сомнениях, что в процессе анализа какие-то кейсы не учла, то взяла бы готовые таблицы простых чисел и делителей чисел в качестве правильных ответов для тестов. Если код правильно будет работать на диапазоне чисел от 3 до 1000, то и на миллионах тоже будет ок.
Пы.сы. Еще одна мысль вертится, что если в результате деления четного делимого на 2 мы получим простое число, то это тоже нам может сократить вычисления. Но пока не поняла как это можно эффективно использовать и на каком шаге. Вроде этот факт нам никак жизнь не облегчит, а может я ошибаюсь
1) Можно применить решето Эратосфена и из искомого диапазона вычеркнуть сразу все простые числа, чтобы не тратить время на проверку каждого из них на множественные делители.
2) Может стоит искать делители не последовательно, а рассматривать четность/нечетность делимого, делителя и частного.
Тут же не сказано в условии, что именно 5 наименьших делителей
Потенциальные делители тогда сверху сможем ограничить корнем квадратным из делимого, а значит еще сократить перебор.
Если число делится на 2 без остатка, то частное может быть четным и нечетным.
Например, 35000002 поделенное на 2 это 17500001. Получается, что при делении на 2 мы нашли один из искомых нечетных делителей. Но при этом каждый раз нам надо проверять четность частного, а это дополнительная операция.
Так же может стоит для оптимизации алгоритма рассмотреть является ли делимое четным числом или нет, чтобы еще сузить круг потенциальных делителей.
Что мы имеем:
1) четное / четное - не можем судить о нечетности результата: может быть четным и нечетным
Следовательно, четные делимые имеет смысл проверять на деление на 2 и на степени числа 2.
Степенями двойки выявим делители типа таких 35000000 / 64 что дает 546875
2) четное / нечетное - если делится нацело, то результат всегда четный.
3) нечетное / четное - результат не будет целым числом. Следовательно, нечетные делимые нет смысла гонять по набору четных делителей.
4) нечетное / нечетное - если результат целое число, то нечетное. Следовательно, в этом случае наш счетчик нечетных делителей получает сразу +2 найденных нечетных делителя. Здесь даже контролировать четность частного дополнительной операцией не нужно.
В итоге имеем:
ШАГ 1: Выявляем и сохраняем массив простых чисел из искомого диапазона с помощью решета Эратосфена
ШАГ 2: проверяем делимое на четность. Тут е
Для нечетных делимых:
ШАГ 3: Проверяем есть ли это делимое в нашем массиве простых чисел или нет. Если нет, то:
ШАГ 4: Проверяем делимость на нечетные числа, которые меньше или равны корню квадратному из делимого. Помним, что каждый найденный делитель нам дает +2 к счетчику. Если не набрали искомое число делителей, то ответ “Нет”, если набрали - “Да”
Для четных делимых:
ШАГ 3: Проверяем делимость на нечетные числа, которые меньше или равны корню квадратному из делимого, при этом контролируем четность остатка, чтобы не пропустить комбинацию нечетное х нечетное = четное. Если нашли нужное количество делителей, выводим “да”, иначе шаг 4
ШАГ 4. Дополнительно проверяем четными делителями, а именно степенями числа 2. Если так и не нашлись, то выводим “Нет”, если нашлись, выводим “Да”.
Чтобы каждый раз не строить ряд нечетных делителей и степеней числа 2, их тоже можно вынести в отдельный шаг и сохранить как массив чисел. Рассчитать их до корня квадратного верхней границы диапазона включительно.
Так как я всегда в сомнениях, что в процессе анализа какие-то кейсы не учла, то взяла бы готовые таблицы простых чисел и делителей чисел в качестве правильных ответов для тестов. Если код правильно будет работать на диапазоне чисел от 3 до 1000, то и на миллионах тоже будет ок.
Пы.сы. Еще одна мысль вертится, что если в результате деления четного делимого на 2 мы получим простое число, то это тоже нам может сократить вычисления. Но пока не поняла как это можно эффективно использовать и на каком шаге. Вроде этот факт нам никак жизнь не облегчит, а может я ошибаюсь
Ocean чесно говоря там все чутка сложнее и одновременно проще. Чисто эмпирически выяснилось “5 различных нечетных делителя” могут быть только в том случае если число имеет целочисленный корень. Математику под это к сожалению я не могу подвести. Так что просто проверяем если число не имеет целого корня, то отбрасываем его, если имеет то ищем все делители. Итого перебор занимает пару секунд.
LeeА где говорится, что они должны быть одновременно перемножены?
Нужно вывести все числа которые имеют меньше 5 различных нечетных делителя(кол во четных может быть любым).
PEHDOMЯ просто подобрал в калькуляторе Emacs
Так что просто проверяем если число не имеет целого корня, то отбрасываем его, если имеет то ищем все делители.
Делители [4, 163, 53,681]
Число 35,000,012
Корень числа 5,916.08079729
>>> n = 35000012 >>> for i in range(1, n + 1): ... if n % i == 0 and i % 2 != 0: ... print(n, '->', i) ... 35000012 -> 1 35000012 -> 163 35000012 -> 53681 35000012 -> 8750003 >>>
К корню, решету Эратосфена и подобным вещам вы можете приставать, если там речь идёт про простые числа. А иначе вы просто потеряете где-то либо делители, либо числа. И этот крендель получит двойку на ЕГЭ в итоге.
py.user.nextО пардонте, это другая задача, очень похожая но там нужно было найти ровно 5 нечетных делителей, а тут менее пяти, , невнимательно прочитал. Тогда оно конечно не подходит.
Поздравляю, ты выкинул подходящее число.
PEHDOMТам много похожих задач и ещё их все разбирают по винтикам учителя информатики на YouTube'е. Лень просто всё это просматривать. Здесь, я так понял, нельзя фокусироваться на этом конкретном рассматриваемом диапазоне от 35000000 до 40000000 и использовать какие-то его свойства, присущие только ему, потому что в любой момент они могут взять и поменять диапазон на другой и сказать “а вот теперь для этого диапазона найдите всё то же самое”, из-за чего всё решение сразу посыпется, потому что чудесные свойства диапазона исчезнут. Так что, думаю, тут нужно брать число из диапазона и что-то с ним делать. Тогда такой привязки к диапазону не будет и там будет всё равно, какой диапазон чисел берётся.
это другая задача, очень похожая но там нужно было найти ровно 5 нечетных делителей
Тут есть вещи, которые могут пригодиться
wiki. делимости
Но я думаю, нужно число поделить на два и потом сверху вниз двигаться. Может, ещё признаки делимости привлечь для этого. Да и единица тоже является нечётным делителем, поэтому мне непонятно, почему её решили исключать из этих пяти делителей? Ну и что, что единица. Нормальный делитель, ничем не хуже других. И само число, если оно нечётное, тоже является своим делителем нечётным.
Add
Убрал критерий “через одно”.
Добавил критерий “само число, если нечётное”.
py.user.nextэто не свойства диапазона, это свойства нечетного количества делителей, число имеет нечетное количество делителей если имеет целочисленный корень. Там дальше наверно еще какаято математика, но я ее не могу сейчас привети. Типа того что если количество делителей четное, то и количество, нечетных делителей тоже четное. но повторюсь подвести под это математику я сейчас не могу. Чисто эмпирическионо выходит так, причем диапазон достаточно большой чтобы не считать что это свойство присуще исключительно текущему диапазону.
Здесь, я так понял, нельзя фокусироваться на этом конкретном рассматриваемом диапазоне от 35000000 до 40000000 и использовать какие-то его свойства, присущие только ему, потому что в любой момент они могут взять и поменять диапазон на другой и сказать “а вот теперь для этого диапазона найдите всё то же самое”, из-за чего всё решение сразу посыпется, потому что чудесные свойства диапазона исчезнут.
py.user.nextДа я все это смотрел уже, признаки делимости они хорошо себя показывают для решения в уме/тетрадке, но не в коде. Допустим признак делимости на 9: если сумма всех чисел делиться на 9. Тоесть нам нужно сначала Х-значное число разбить на X цифр,(в пайтоне это еще просто, по крайней мере с точки зрения написания кода, а в каконить условном паскале придеться сделать Х операций целочисленного деления) потом просумvировать их и посмотреть делятся они без остатка на 9… не проще ли, с точки зрения быстродействия, просто сразу посмотреть делиться ли число на 9 без остака? без всех этих преобразований и прочего.
Тут есть вещи, которые могут пригодиться
Учитывая достаточно большой диапазон, тут должен быть какойто критерий позволяющий просто отбросить большую часть чисел..
py.user.nextусловности
Да и единица тоже является нечётным делителем, поэтому мне непонятно, почему её решили исключать из этих пяти делителей? Ну и что, что единица. Нормальный делитель, ничем не хуже других.
py.user.nextтоже не вариант, ведь поделив на четное вплолне можем получить нечетное… перебором оно решается делением на (от 2 до int(корня квадратного из числа))
Но я думаю, нужно число поделить на два и потом сверху вниз двигаться через одно число по нечётным.
Oceanнаверно можно но сильно сомневаюсь что в искомом диапазоне их будет сильно много, гугел говорит что примерно 800 на миллион. тоесть мы отсеем менее 0.01% всех чисел, это не сильно ускорит алгоритм.
Можно применить решето Эратосфена и из искомого диапазона вычеркнуть сразу все простые числа, чтобы не тратить время на проверку каждого из них на множественные делители.
Ускорить можно если перебирать не весь диапазон, а только от 2-х до корня квадратного из числа, это ускоряет на данном диапазоне процесс почти в шесть тысяч раз, но всеравно выходит достаточно долго, чтото около 15-ти минут на миллион, а у нас их 5.
тут должно быть чтото простое и очевидное, просто на ум не приходит.