|
8 / 7 / 1
Регистрация: 08.04.2021
Сообщений: 151
|
||||||
Найти количество и сумму всех натуральных делителей числа20.06.2021, 13:52. Показов 13169. Ответов 36
Числовые функции
Количество всех натуральных делителей натурального числа n обозначается σ0(n). Сумма всех натуральных делителей числа n обозначается σ1(n). Входные данные Дано натуральное n≤109. Выходные данные Выведите σ0(n) и σ1(n). Примечание Данную задачу рекомендуется решать путём перебора всех делителей числа до n−−√. Примеры Ввод Вывод 6 4 12 Вот мой код:
0
|
||||||
| 20.06.2021, 13:52 | |
|
Ответы с готовыми решениями:
36
Составить программу, которая вычисляет количество S всех делителей и сумму Y всех делителей натурального числа N
|
| 22.06.2021, 21:40 | ||
|
Дубли возникать будут, и сет нужен.
Красота - в глазах смотрящего, и если вкус испорчен убогостью С++ и СТЛ, тогда это предсказуемо сказывается на субъективных оценках Если факторизация уже есть в наличии - тогда да, но при этом наличествует
0
|
||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,407
|
||
| 23.06.2021, 00:18 | ||
|
Тему я рассматривал здесь. Количество делителей по факторизации определяется мгновенно. Сам делители тоже формируются итеративно и гарантированно без повторений путем итеративного перебора всех возможных комбинаций степеней факторов.
0
|
||
| 23.06.2021, 00:42 | |
|
Можете не повторяться, я прекрасно все понял с первого раза
Все правильно, в вашем алгоритме все так (если аккуратно обработать корнер-кейсы, отдельно потом добавить 1-цу к делителям минуя факторы и т.п.). А в моем, который вы изволили охарактеризовать уродливым - есть необходимость хранить и накапливать множество делителей, зато нет нужды хранить состав факторизации (да, я в курсе, что он меньше множества делителей). И наверное даже ваш алгоритм будет быстрее (на пару милисекунд при земных числах). При неземных числах возможно это будет даже иметь смысл.
0
|
|
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
||||||||||||
| 23.06.2021, 11:55 | ||||||||||||
|
Крч поиск простых - фтопку, слишком жирно тут; это, возможно, как-то могло бы иметь смысл для обсчёта большого кол-ва чисел, накапливая список простых для след. использования.
Склеил такое: Кликните здесь для просмотра всего текста
Результаты совпадают, раза в 1.5 - 2 медленнее чем #9, но на пару порядков шустрее чем с простыми ![]()
0
|
||||||||||||
| 23.06.2021, 12:57 | |||||||||||
|
Folian, не знаю как вы сделали, но я имел в виду вот это (на С++ неудобно, поэтому на Clojure)
![]() Финальные
1
|
|||||||||||
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
|||||||
| 24.06.2021, 19:25 | |||||||
![]() Происходит тут, значит, нечто такое:
0
|
|||||||
| 24.06.2021, 19:46 | |
|
А в С++ нельзя итерироваться по коллекции, в которую добавляешь элементы по ходу итерации? Что-то припоминаю такое, что вроде можно. Тогда не нужны эти временные сеты, можно прямо в результат инсертить и будет так же красиво как в Кложе
Но конечно алгоритм на предыдущей странице (он же из стартового поста ТС, он же из комментария в тексте задачи) более оптимален (в общем случае, в частном случае чисел, факторизующихся в малые по значению сомножители, он может быть менее оптимален)
0
|
|
|
Гвоздь Задиров
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
|
||
| 24.06.2021, 19:57 | ||
, но на векторе/его вариациях итераторы могут чаще ломаться(там перевыделение памяти может бывать и так лучше не делать). Я чуть выше тут уже так сделал, тут просто более или менее "дословно" пытался перевести то что понял как в Clojure происходит.
1
|
||
| 25.06.2021, 00:14 | ||
Поэтому итерируясь по изначальной коллекции и получая на ее основе новую апдейтную (не меняя исходную) мы обходимся без копирования общих частей обоих коллекций. Но это уже тему совсем в другую степь уводим. Хотя это и позволяет написать весь алгоритм одной красивой короткой строчкой свертки
1
|
||
| 25.06.2021, 02:04 | |
|
0
|
|
|
8 / 7 / 1
Регистрация: 08.04.2021
Сообщений: 151
|
|
| 28.06.2021, 13:42 [ТС] | |
|
Я - новичок, так что последние сообщения на 70% не понимаю. Разобралась сама, всем спасибо.
0
|
|
|
11 / 10 / 1
Регистрация: 27.07.2022
Сообщений: 9
|
|
| 27.07.2022, 17:53 | |
|
...
0
|
|
|
0 / 0 / 0
Регистрация: 20.06.2022
Сообщений: 30
|
|
| 29.07.2022, 05:27 | |
|
У каждого делителя d числа n, который меньше n−−√ есть парный ему, равный n/d, больший n−−√. Будем учитывать их парами. Еще нужно не забыть, что если n−−√ является делителем, то у него нет пары.
Добавлено через 1 минуту У каждого делителя d числа n, который меньше n−−√ есть парный ему, равный n/d, больший n−−√. Будем учитывать их парами. Еще нужно не забыть, что если n−−√ является делителем, то у него нет пары.HWAA,
0
|
|
|
11 / 10 / 1
Регистрация: 27.07.2022
Сообщений: 9
|
||||||
| 03.08.2022, 11:44 | ||||||
|
не мучайте себя, вот может подойдёт
0
|
||||||
|
0 / 0 / 0
Регистрация: 26.08.2024
Сообщений: 2
|
||||||
| 26.08.2024, 20:15 | ||||||
0
|
||||||
|
Вездепух
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,407
|
|
| 26.08.2024, 21:46 | |
|
Собственно, не ясно, зачем в обсуждении выше зашла речь о фактическом поиске самих делителей (кроме странной рекомендации из условия задачи).
Такие задачи рассчитаны на понимание следующих фактов: 1. Функции σ0(n) и σ1(n) - мультипликативны 2. Значения σ0(pk) и σ1(pk) для простого p вычисляются тривиально То есть задача прекрасно решается через факторизацию значения n на простые множители.
0
|
|
|
Нарушитель
6700 / 3112 / 1064
Регистрация: 01.06.2021
Сообщений: 12,023
|
||
| 26.08.2024, 23:27 | ||
|
а вот чисто ради научного интереса, можно и инициировать побочные дискуссии для выявления лучших алгоритмов...
0
|
||
| 26.08.2024, 23:27 | |
|
Найти число и сумму натуральных делителей числа m
Найти сумму всех делителей числа А
Используя процедуру нахождения количества натуральных делителей числа, определить у какого из трех чисел натуральных делителей больше Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С.
Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
|
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию?
Фраза «Любая достаточно развитая технология неотличима от магии». . .
|
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль?
Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
|
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология.
«Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
|
|
Генератор паролей (вариант №2)
Maks 30.10.2026
Обновленная версия ранее созданной обработки.
Добавлены следующие реквизиты типа Булево:
- Буквы;
- Цифры;
- Символы.
Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .
|
Генератор паролей (вариант №1)
Maks 29.10.2026
Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей.
Самым главным критерием для. . .
|
Установка ChatGPT (Codex) на Windows без использования Microsoft Store
Fabien159 28.10.2026
Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store.
И так:
1. Скачиваем с. . .
|
Программное добавление префикса в нумерацию документов
Maks 27.10.2026
Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге).
Задача:
Программно добавить префикс в нумерацию документов.
Решение:
В модуле объекта. . .
|