Алгоритм проверки числа на "совершенность"

@Naudiz · Регистрация: 04.11.2011

Студворк — интернет-сервис помощи студентам

Приветствую всех!

Прошу помочь со следующей задачей:

"Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 6 – совершенное, так как 6 = 1+2+3. Число 8 – не совершенное, так как 8 ≠ 1+2+4.Дано натуральное число n. Получить все совершенные числа, меньшие n."

Задачу я решил (код ниже), но работает программа слишком медленно. Пожалуйста помогите оптимизировать код, нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.

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;
 
bool perfect(int x)
{
   int sum=0;
   for (int i=1; i<x; i++)
      if (x%i==0) sum+=i;
   if (x==sum) return 1;
   return 0;
}
 
int main()
{
   int x;
   cin >> x;
   for (int i=1; i<=x; i++)
      if (perfect(i)) cout << i << endl;
   return 0;
}

Ссылки на литературу по сабжу приветствуются.

Заранее всем благодарен))

@Thinker · 09.07.2013, 20:04

Сообщение от Toshkarik

Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.

Спасибо, что понимаете

в том алгоритме по сути не используется свойство:
если a делитель n, то и n/a тоже делитель, там еще более крутые моменты (мультипликативные функции), поэтому быстро работает

P.S. а то бы не выставлял бы тот алгоритм. интересно было поработать с мульт.функциями, после чего пришла идея такого алгоритма.

ValeryS · 09.07.2013, 20:18

Сообщение от Kukurudza

Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение.

не совсем уверен

i5 нет проверить не могу
но до него div достаточно дорогая операция была

Сообщение от Kukurudza

как она реадизована я не в курсе

очень часто деление заменяется на умножение и сдвиг

@Toshkarik · 09.07.2013, 20:23

Kukurudza, я что то разве говорил об умножении? Я сравнивал с битовыми операциями.

@Naudiz · 10.07.2013, 09:36 **[ТС]**

ValeryS, спасибо за замечания)) Сразу как-то и не подумал над х/2.
Чуть-чуть причесал код:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
bool perfect(unsigned int x)
{
   unsigned int sum=0;
   for (int i=1; i<=x/2; i++)
      if (x%i==0) sum+=i;
   return x==sum;
}
 
int main()
{
   unsigned int x;
   std::cin >> x;
   for (unsigned int i=4; i<=x; i++)
      if (perfect(i)) std::cout << i << std::endl;
   return 0;
}

Kukurudza, благодарю за вики, появились кое какие мысли) Использование последовательности чисел Мерсенне способ весьма годный на практике, но когда речь идёт об алгоритмизации думаю не совсем уместен.

Сообщение от Kukurudza

реализованный алгоритм имеет нотацию O(n*n)

Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?

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

Вообщем по алгоритму проверки числа на совершенность пока идей больше нет, а вот как сократить количество итераций проверки самих чисел меньше заданного n (по условию) есть. Заинтересовало сл. св-во совершенных чисел в вики:
"Все чётные совершенные числа в двоичной записи содержат сначала p единиц, за которыми следует p—1 нулей (следствие из их общего представления)."

Таким образом можно было бы проверять все числа от 4 до n сначала на удовлетворение этому условию (операция, как я полагаю, менее затратная, если не ошибаюсь) и только проходящие по нему проверять на совершенность.

@Thinker · 10.07.2013, 09:39

Сообщение от Naudiz

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

Спасибо, всякую фигню бы не стал выставлять на показ

Возможно, оптимизирую его как-нибудь.

@Kukurudza · 10.07.2013, 10:02

Сообщение от Naudiz

Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?

ей богу, у меня иногда складывается мнение что только у меня гугл разбанен:
http://ru.wikipedia.org/wiki/%... 0%B8%D1%8F
а вообще это у вас академическая задача или какая-то практическая? решили нобеля получить поди?

@Stereotip · 10.07.2013, 10:17

если интересно разобраться с О( ) и с другими её друзьями - "Алгоритмы построения и анализ" авторы: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн)

@Thinker · 10.07.2013, 12:31

Naudiz,
Быстрый поиск совершенных чисел

@Naudiz · 12.07.2013, 20:50 **[ТС]**

Thinker, благодарю, то что нужно. Можно вопрос по Вашему коду?

C++
1
const unsigned long long N = 5000000000000000000llu; //3я строка

Что значит "llu"?

Эта запись в дальнейшем фигурирует в выражениях в main

@Thinker · 12.07.2013, 20:53

Сообщение от Naudiz

Что значит "llu"?

Эта запись в дальнейшем фигурирует в выражениях в main

везде llu замените на ull это константа типа unsigned long long

@Dani · 12.07.2013, 20:57

Самый быстрый поиск совершенных чисел. Берем гугл. Сбиваем "OEIS совершенные числа". Находим эту страницу - http://oeis.org/A000396 Копируем все числа в константы (хоть в строковые). Организуем поиск по константам. Радуемся сложности O(1)

@Naudiz · 12.07.2013, 21:03 **[ТС]**

Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))

Добавлено через 45 секунд
Dani, не смешно.

@Thinker · 12.07.2013, 21:04

Сообщение от Naudiz

Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))

тогда оставьте. ull нужно для работы с огромными типизированными константами, в противном случае число 50...0 просто урежется.

@Dani · 12.07.2013, 21:07

Сообщение от Naudiz

Dani, не смешно.

Никто шутить и не собирался. Работает быстро и правильно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
#include <algorithm>
 
int main()
{
    const std::string arr[] = {"6","28","496","8128","33550336","8589869056","137438691328","2305843008139952128","2658455991569831744654692615953842176",
        "191561942608236107294793378084303638130997321548169216"}; //совершенные числа
    const int len = 10; //количество совершенных чисел
    std::string inp_number;
    std::cin >> inp_number;
    std::cout << ( std::find(arr, arr+len, inp_number) != arr+len ? "It is perfect number" : "It is not perfect number") << std::endl;
    return 0;
}

@Thinker · 12.07.2013, 21:12

Dani, программа дает иллюзию, что что ты сам их находишь

@Dani · 12.07.2013, 21:13

Thinker, Зато 10 чисел найдет

В отличии от других программ.

@Naudiz · 12.07.2013, 21:15 **[ТС]**

Dani, речь идёт именно об "алгоритме проверки числа на совершенность", а не о выводе совершенных чисел на экран.

Thinker, а что происходит в 57 строке? Заранее извиняюсь, мне еще не по зубам такой код(

@Dani · 12.07.2013, 21:16

Naudiz, здесь и проверяется число на совершенность, как ты мог заметить.

@Thinker · 12.07.2013, 21:19

Dani, программа дает иллюзию, что если вдруг ОЗУ позволит хранить очень большие числа, то с ее помощью можно найти еще несколько дополнительных чисел, не вошедших в ТОП10

Добавлено через 2 минуты

Сообщение от Naudiz

Thinker, а что происходит в 57 строке?

это просто. с помощью побитовых операций вычисляем значение
$https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{i-1}(2^i-1)$

@Dani · 12.07.2013, 21:23

Сообщение от Thinker

программа дает иллюзию

но она ведь правильно проверяет число на совершенность. что и требовалось

Сообщение от Naudiz

нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.

Что ТС просил - все условия выполняются.
Если нужно научиться находить совершенные числа или в учебных целях - то с твоим кодом никто не конкурирует, но пусть большие числа считает, например, этот сайт http://oddperfect.org/
Да и BigInt юзать как-то неохота в связи с затратами и повышением сложности кода.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	09.07.2013, 20:23
	Kukurudza, я что то разве говорил об умножении? Я сравнивал с битовыми операциями. 0

@Stereotip 2 / 2 / 1 Регистрация: 17.04.2012 Сообщений: 22
	10.07.2013, 10:17
	если интересно разобраться с О( ) и с другими её друзьями - "Алгоритмы построения и анализ" авторы: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн) 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	10.07.2013, 12:31
	Naudiz, Быстрый поиск совершенных чисел 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 20:57
	Самый быстрый поиск совершенных чисел. Берем гугл. Сбиваем "OEIS совершенные числа". Находим эту страницу - http://oeis.org/A000396 Копируем все числа в константы (хоть в строковые). Организуем поиск по константам. Радуемся сложности O(1) 0

@Naudiz 16 / 14 / 7 Регистрация: 04.11.2011 Сообщений: 137
	12.07.2013, 21:03 [ТС]
	Thinker, не понял. В Вашем коде именно llu и он компилируется и работает)) Добавлено через 45 секунд Dani, не смешно. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	12.07.2013, 21:12
	Dani, программа дает иллюзию, что что ты сам их находишь 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 21:13
	Thinker, Зато 10 чисел найдет В отличии от других программ. 0

@Naudiz 16 / 14 / 7 Регистрация: 04.11.2011 Сообщений: 137
	12.07.2013, 21:15 [ТС]
	Dani, речь идёт именно об "алгоритме проверки числа на совершенность", а не о выводе совершенных чисел на экран. Thinker, а что происходит в 57 строке? Заранее извиняюсь, мне еще не по зубам такой код( 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 21:16
	Naudiz, здесь и проверяется число на совершенность, как ты мог заметить. 0