Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.53/57: Рейтинг темы: голосов - 57, средняя оценка - 4.53
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

Вот мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
void f(long long num) {
long long counter(1), sum(1);
for (int i = 2; i * i <= num; ++i)if (!(num % i)) {
sum += i + (num / i);
counter += 2;
}
++counter;
sum += num;
cout << counter << " " << sum;
}
 
int main()
{
long long num;
cin >> num;
f(num);
return 0;
}
Система говорит неправильный ответ, не пойму понять в чем ошибка. Помогииите пожалуйста
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
20.06.2021, 13:52
Ответы с готовыми решениями:

Составить программу, которая вычисляет количество S всех делителей и сумму Y всех делителей натурального числа N
1. Дано натуральное число N (N&lt;104). Составить программу, которая вычисляет количество S всех делителей и сумму Y всех делителей...

В выходной файл OUTPUT.TXT выведите сумму всех натуральных делителей числа n
Как и многие другие девочки, Маша любит разные гадания. Некоторое время назад Маша узнала новый способ гадать на числах – для какого-нибудь...

Дано натуральное число, найти сумму всех его натуральных делителей
1.) Процедуры и функции. Даны отрезки a,b,c,d для каждой тройки этих отрезков, из которых можно построить треугольник написать площадь...

36
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
22.06.2021, 21:40
Студворк — интернет-сервис помощи студентам
Дубли возникать будут, и сет нужен.
Красота - в глазах смотрящего, и если вкус испорчен убогостью С++ и СТЛ, тогда это предсказуемо сказывается на субъективных оценках
Если факторизация уже есть в наличии - тогда да, но при этом наличествует
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
необходимость хранить предыдущие результаты
, что как-бы считается некрасивым. А алгоритм с сетом может редьюсить поток факторов от алгоритма факторизации, без получения полного набора факторов.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13235 / 6867 / 1827
Регистрация: 18.10.2014
Сообщений: 17,407
23.06.2021, 00:18
Цитата Сообщение от _Ivana Посмотреть сообщение
Если факторизация уже есть в наличии - тогда да, но при этом наличествует
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
необходимость хранить предыдущие результаты
что как-бы считается некрасивым.
Необходимость хранить саму факторизацию есть. В упор не вижу необходимости хранить что-то еще или что-то отсеивать.

Тему я рассматривал здесь. Количество делителей по факторизации определяется мгновенно. Сам делители тоже формируются итеративно и гарантированно без повторений путем итеративного перебора всех возможных комбинаций степеней факторов.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.06.2021, 00:42
Можете не повторяться, я прекрасно все понял с первого раза Все правильно, в вашем алгоритме все так (если аккуратно обработать корнер-кейсы, отдельно потом добавить 1-цу к делителям минуя факторы и т.п.). А в моем, который вы изволили охарактеризовать уродливым - есть необходимость хранить и накапливать множество делителей, зато нет нужды хранить состав факторизации (да, я в курсе, что он меньше множества делителей). И наверное даже ваш алгоритм будет быстрее (на пару милисекунд при земных числах). При неземных числах возможно это будет даже иметь смысл.
0
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
23.06.2021, 11:55
Крч поиск простых - фтопку, слишком жирно тут; это, возможно, как-то могло бы иметь смысл для обсчёта большого кол-ва чисел, накапливая список простых для след. использования.

Склеил такое:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    size_t value = 0;
    std::cin >> value;
 
    size_t half = value / 2;
    size_t hold = value;
 
    std::set<size_t> st;
    
    for(size_t x = 2; value >= x; ++x)
    {
        size_t temp = x;
        while(!(value % x))
        {
            st.insert(temp);
            temp *= x;
            value /= x;
        }
    }
    
    for(auto it = st.begin(); it != st.end(); ++it)
    {
        auto next = it;
        while(++next != st.end())
        {
            size_t temp = *it * *next;
            if(temp > half) break;
            if(!(hold % temp)) st.insert(temp);
        }
    }
 
    st.insert(1);
    st.insert(hold);
 
    size_t sum = 0;
    for(auto i : st)
    {
        std::cout << i << " ";
        sum += i;
    }
    std::cout << "\n\n" << st.size() << " " << sum << "\n\n";

Результаты совпадают, раза в 1.5 - 2 медленнее чем #9, но на пару порядков шустрее чем с простыми

Цитата Сообщение от _Ivana Посмотреть сообщение
там напрашивается красивый итерационный алгоритм получения всех возможных произведений набора сомножителей - итерируемся по списку сомножителей, на каждой итерации имеем текущий список возможных произведений (можно сразу в сете, для исключения дублей), и обновляем этот сет, оставляя все имеющиеся элементы, добавляя произведение всех имеющихся на текущий сомножитель и сам текущий сомножитель.
Мож я чё не так сделал, но, кмк, не очень красиво вышло, т.к., например, вот это понадобилось:
C++
1
if(!(hold % temp)) st.insert(temp);
Т.к., к примеру, 450 на 12 не делится, а оно всплывёт иначе.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.06.2021, 12:57
Folian, не знаю как вы сделали, но я имел в виду вот это (на С++ неудобно, поэтому на Clojure)
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  (defn factor [n]
    (let [go (fn go [n i]
               (cond
                 (> (* i i) n) (list n)
                 (zero? (rem n i)) (lazy-seq (cons i (go (quot n i) i)))
                 :else (go n (inc i))))]
      (go n 2)))
 
  (->> 450
       factor
       (reduce (fn [acc n] (into acc (map #(* % n) acc))) #{1})
       sort
       vec)
 
=> [1 2 3 5 6 9 10 15 18 25 30 45 50 75 90 150 225 450]
, никаких 12 не всплывает

Финальные
Lisp
1
2
sort
vec)
не нужны, добавлены исключительно для красивой визуализации результата
1
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
24.06.2021, 19:25
Цитата Сообщение от _Ivana Посмотреть сообщение
поэтому на Clojure
Пришлось потратить пару часов чтоб понять что тут написано, но было интересно
Происходит тут, значит, нечто такое:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    std::multiset<size_t> st;
    for (size_t x = 2; value >= x; ++x)
        while (!(value % x))
        {
            st.insert(x);
            value /= x;
        }
 
    std::set<size_t> result_set{1};
    for(const auto &src_seq : st)
    {
        std::set<size_t> temp;
        for(auto &c_seq : result_set)
            temp.insert(c_seq * src_seq);
        for(const auto &i : temp) result_set.insert(i);
    }
Идею понял, можно, конечно, подкрутить, но, кмк, всё равно лучше уж сразу брать отсюда.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
24.06.2021, 19:46
А в С++ нельзя итерироваться по коллекции, в которую добавляешь элементы по ходу итерации? Что-то припоминаю такое, что вроде можно. Тогда не нужны эти временные сеты, можно прямо в результат инсертить и будет так же красиво как в Кложе Но конечно алгоритм на предыдущей странице (он же из стартового поста ТС, он же из комментария в тексте задачи) более оптимален (в общем случае, в частном случае чисел, факторизующихся в малые по значению сомножители, он может быть менее оптимален)
0
Гвоздь Задиров
 Аватар для Folian
1719 / 1118 / 337
Регистрация: 25.01.2019
Сообщений: 2,946
24.06.2021, 19:57
Цитата Сообщение от _Ivana Посмотреть сообщение
нельзя итерироваться по коллекции, в которую добавляешь элементы по ходу итерации?
Можно во всяких сетах/списках если специально в ноги не целиться , но на векторе/его вариациях итераторы могут чаще ломаться(там перевыделение памяти может бывать и так лучше не делать). Я чуть выше тут уже так сделал, тут просто более или менее "дословно" пытался перевести то что понял как в Clojure происходит.
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
25.06.2021, 00:14
Цитата Сообщение от Folian Посмотреть сообщение
в Clojure происходит
чуть более сильная магия, там структуры данных иммутабельны, но при этом персистентны (эффективно шарят без копирования свои общие части при апдейтах) Поэтому итерируясь по изначальной коллекции и получая на ее основе новую апдейтную (не меняя исходную) мы обходимся без копирования общих частей обоих коллекций. Но это уже тему совсем в другую степь уводим. Хотя это и позволяет написать весь алгоритм одной красивой короткой строчкой свертки
1
25.06.2021, 02:04

Не по теме:

Цитата Сообщение от _Ivana Посмотреть сообщение
чуть более сильная магия
Ага, заметил что там много колдунства всякого подобного, но до дна копать цели не было)
Цитата Сообщение от _Ivana Посмотреть сообщение
Но это уже тему совсем в другую степь уводим.
Да, раздел явно не про это))

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
не мучайте себя, вот может подойдёт

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    unsigned long long int x;
    cin >> x;
    unsigned long long int sum = 0, k=0;
    for (int i = 1; i <= sqrt(x); i++)
    {
        if (i * i == x)
        {
            sum += i;
            k++;
        }
        else if (x % i == 0)
        {
            sum += i;
            sum += x / i;
            k++;
            k++;
        }
    }
    cout << k <<" " << sum << endl;
    return 0;
}
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    unsigned long long int x;
    cin >> x;
    unsigned long long int sum = 0, k=0;
    for (int i = 1; i <= sqrt(x); i++)
    {
        if (i * i == x)
        {
            sum += i;
            k++;
        }
        else if (x % i == 0)
        {
            sum += i;
            sum += x / i;
            k++;
            k++;
        }
    }
    cout << k <<" " << sum << endl;
    return 0;
}
0
0 / 0 / 0
Регистрация: 26.08.2024
Сообщений: 2
26.08.2024, 20:15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
using namespace std;
 
 
int main()
{
    int x;
    cin >> x;
    int kol = 0, k = 1;
    long long sum = 0;
    while (k*k <= x){
        if ((x % k) == 0){
            if (k*k == x){
                kol += 1;
                sum += k;
            }
            else{
                kol += 2;
                sum += k + (x/k);
            }
        }
        k+=1;
    }
    cout << kol << " " << sum;
    return 0;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
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
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
кроме странной рекомендации из условия задачи
в любом случае, ответом в данной теме может быть решение, которое соблюдает условие задачи, насколько странным оно ни было

а вот чисто ради научного интереса, можно и инициировать побочные дискуссии для выявления лучших алгоритмов...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
26.08.2024, 23:27

Найти число и сумму натуральных делителей числа m
Найти число и сумму натуральных делителей числа m m=1670

Найти сумму всех делителей числа.
5. Найти сумму всех делителей числа.

Найти сумму всех делителей числа А
5.Найти сумму всех делителей числа А.

Процедуры и функции. Найти сумму всех делителей числа
Найти сумму всех делителей числа

Используя процедуру нахождения количества натуральных делителей числа, определить у какого из трех чисел натуральных делителей больше
Используя процедуру нахождения количества натуральных делителей числа, определить у какого из трех чисел натуральных делителей больше


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Новые блоги и статьи
Генератор паролей (вариант №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
Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru